#include <bits/stdc++.h>
#define INF 1<<30
#define nmax 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,s,x,y,c,d[nmax],m,i,k,min1;
vector <pair<int,int> >v[nmax];
bool viz[nmax];
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));
        if(x==1)
            d[y]=c;

    }
    s=1;//nodul radacina

    viz[s]=1;
    d[s]=0;
    d[0]=INF;

    for(k=1; k<n; k++)
    {
        min1=0;
        for(i=1; i<=n; i++)
            if(!viz[i]&&d[i]<d[min1])
                min1=i;
        if(min1)
        {
            viz[min1]=1;
            for(i=0; i<v[min1].size(); i++)
            {
                x=v[min1][i].first;
                if(!viz[x]&&d[x]>d[min1]+v[min1][i].second)
                    d[x]=d[min1]+v[min1][i].second;
            }
        }

    }

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

    return 0;
}