#include<fstream>
using namespace std;
ifstream cin("Dijkstra.in");
ofstream cout("Dijkstra.out");
int Q[50005],D[50005],n,m,x,y,z,minim,pmin;
struct graf{
    int nod,cost;
    graf *next;
};
graf *G[50005];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        graf *q=new graf;
        q->nod=y; q->cost=z; q->next=G[x]; G[x]=q;
    }
    for(int i=2;i<=n;i++)
        D[i]=~(1<<31);
    for(int i=1;i<=n;i++)
    {
        minim=~(1<<31);
        for(int j=1;j<=n;j++)
            if(!Q[j] && D[j]<minim)
        {
            minim=D[j];
            pmin=j;
        }
        Q[pmin]=1; graf *t=G[pmin];
        while(t)
        {
            if(D[t->nod]>D[pmin]+t->cost)
                D[t->nod]=D[pmin]+t->cost;
            t=t->next;
        }
    }
    for(int i=2;i<=n;i++)
        if(D[i]==~(1<<31)) cout<<"0 ";
        else cout<<D[i]<<' ';
}