#include <bits/stdc++.h>
#define INF 1<<30
#define nmax 50001
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,s,x,y,c,d[nmax],m,i,k,min1,l,nod;
vector <pair<int,int> >v[nmax];
typedef pair<int,int> tip;
priority_queue <tip,vector<tip>,greater<tip> > q;
bool viz[nmax];
//am priority queue ordonata descrescator-elementul top o sa fie mereu cel mai mic
int main()
{
    f>>n>>m;

    for(i =1 ; i <= n ; i ++ )
        d[i]=INF;

    for(i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));

    }


    d[1]=0;
    q.push({0,1});


while(!q.empty())
    {
        l=q.top().first;
        nod=q.top().second;
        q.pop();

        if(l==d[nod])
            for(i=0;i<v[nod].size();i++)

        {   x=v[nod][i].first;
            if(d[x]>d[nod]+v[nod][i].second)
            {
                  d[x]=d[nod]+v[nod][i].second;
                  q.push({d[x],x});
            }

        }
    }

    for(i=2; i<=n; i++)
        if(d[i]==INF)
            g<<0<<" ";
        else
            g<<d[i]<<" ";

    return 0;
}