#include<stdio.h>
#define usi unsigned short int
const usi N=50001;
struct G {
usi o,c;
G *u;
};
G *g[N],*r;
int m;
usi n,k,t,i,h[N],d[N],f,w,u,p[N],v,j;
void S(usi a,usi b) { h[a]^=h[b]^=h[a]^=h[b]; }
void U(usi w) {
while(w>1) {
int f=w>>1;
if(d[h[f]]<=d[h[w]])
return;
p[h[w]]=f,p[h[f]]=w,S(w,f),w=f;
}
}
int main() {
freopen("dijkstra.in","r",stdin),freopen("dijkstra.out","w",stdout),scanf("%d%d",&n,&m);
while(m--) {
scanf("%d%d%d",&u,&w,&f);
r=new G;
r->o=w,r->c=f,r->u=g[u],g[u]=r;
}
for(i=2;i<=n;i++)
d[i]=p[i]=N;
for(p[1]=h[++k]=1;k;) {
for(t=h[1],S(1,k),p[h[1]]=w=1,k--;w<=k;) {
f=w;
if((w<<1)>k)
break;
f=w<<1;
if(f+1<=k&&d[h[f+1]]<d[h[f]])
f++;
if(d[h[w]]<=d[h[f]])
break;
p[h[w]]=f,p[h[f]]=w,S(w,f),w=f;
}
for(r=g[t];r;r=r->u) {
if(d[r->o]>d[t]+r->c) {
d[r->o]=d[t]+r->c;
for(v=0,j=1;j<=k&&!v;j++)
if(r->o==h[j])
v=j;
if(v)
U(v);
//if(p[r->o]!=N)
//U(p[r->o]);
else
h[++k]=r->o,p[h[k]]=k,U(k);
}
}
}
for(i=2;i<=n;i++)
printf("%d ",d[i]==N?0:d[i]);
}