#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,p,x,y,c;
const int inf=10000000;
vector <pair<int,int> > v[50005];
priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > > srt;
int viz[50005],d[50005];
int main()
{   f>>n>>m;
    while(f>>x>>y>>c)
    {   v[x].push_back({c,y});
    }
    p=1;
    for(int i=1;i<=n;i++) d[i]=inf;
    d[p]=0;
    srt.push(make_pair(0,p));
    while(!srt.empty())
    {   pair<int,int> t=srt.top();
        srt.pop();
        int cost=t.first;
        int nod=t.second;
        if(!viz[nod])
        {   viz[nod]=1;
            vector<pair<int,int> > :: iterator it=v[nod].begin(),sf=v[nod].end();
            for(;it!=sf;it++)
                if(d[it->second]>cost+it->first)
            {   d[it->second]=cost+it->first;
                srt.push({d[it->second],it->second});
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(d[i]!=inf) g<<d[i]<<' ';
        else g<<"-1\n";
    return 0;
}