#include<fstream>
#define INF 0x3f3f3f3f
#define MaxN 50004

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod {
        int info,cost;
        nod *urm;
        };
nod *prim[MaxN], *a;

struct nod_c {
        int inf;
        nod_c *next;
};
nod_c *first,*last,*present;

int n,m,d[MaxN],x,y/*,c[MaxN]*/,u,p,ct,viz[MaxN];

void insert(int x, int y, int c)
{       a=new nod;
        a->info=y;
        a->cost=c;
        a->urm=prim[x];
        prim[x]=a;
}

void insert_q(int x)
{       nod_c *p;
        p=new nod_c;
        p->inf=x;
        p->next=NULL;
        last->next=p;
        last=p;
}

void bellmanFord()
{       nod *q;
        int i,X;
        for(i=1;i<=n;i++) d[i]=INF;
        d[1]=0;
        p=u=1;
        //c[p]=1;
        first=new nod_c;
        first->inf=1;
        first->next=NULL;
        last=first;
        //int nr=1;
        while(first!=NULL)
        {       X=first->inf;viz[X]=0;//p=(p+1)%MaxN;nr--;
                for(q=prim[X];q;q=q->urm)
                        if(d[X]+q->cost<d[q->info])
                        {       d[q->info]=d[X]+q->cost;
                                if(!viz[q->info])
                                {       //u=(u+1)%MaxN;
                                        //c[u]=q->info;
                                        insert_q(q->info);
                                        viz[q->info]=1;
                                        //nr++;
                                }
                        }
                first=first->next;
        }
}

void write()
{       int i;
        for(i=2;i<=n;i++)
        {       if(d[i]!=INF)
                        fout<<d[i]<<' ';
                else    fout<<"0 ";
        }
}

int main()
{       int i;
        fin>>n>>m;
        for(i=1;i<=m;i++)
        {       fin>>x>>y>>ct;
                insert(x,y,ct);
        }
        bellmanFord();
        write();
        return 0;
}