#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");
int n,m,st[50001],fi[50001],nrc,c[500000],k[50001];

struct elem{int a;int b;int c;};
elem v[250001];

bool compar(const elem &x,const elem &y)
{if (x.a<y.a) return false;
if (x.a==y.a&&x.b<y.b) return false;
return true;
}

int main()
{int i,j;
fscanf(f,"%d %d",&n,&m);
for (i=1;i<=m;i++) fscanf(f,"%d %d %d\n",&v[i].a,&v[i].b,&v[i].c);
sort(v+1,v+m+1,compar);
for (i=1;i<=n;i++) {st[i]=1000000;fi[i]=-1;k[i]=1<<25;}
for (i=1;i<=m;i++) {st[v[i].a]=min(st[v[i].a],i);
                    fi[v[i].a]=max(fi[v[i].a],i);}
nrc=1;
c[1]=1;
k[1]=0;

for (i=1;i<=nrc;i++)
            for (j=st[c[i]];j<=fi[c[i]];j++)

                         {if (k[v[j].a]+v[j].c<k[v[j].b]) {k[v[j].b]=k[v[j].a]+v[j].c;
                                                           c[++nrc]=v[j].b;
                                                           }
                          }
for (i=2;i<=n;i++) fprintf(g,"%d ",k[i]);

return 0;
}