#include<stdio.h>
#include<string.h>
FILE *f,*g;
int t[4][250500]; long c[50500],i,n,m,st[500000],dist[50500],y,z,nr,p,u,q,viz[50500],x,fin[50500],inf; 
char cr;
int main()
{ f=fopen("dijkstra.in","r"); g=fopen("dijkstra.out","w");
  fscanf(f,"%ld%ld",&n,&m); 
  for(i=1;i<=m;i++)
   { fscanf(f,"%ld%ld%ld",&x,&y,&z);
     if(c[x]!=0)  { nr++; t[2][fin[x]]=nr; t[1][nr]=y; t[3][nr]=z; fin[x]=nr; }
	 else { nr++; c[x]=nr; t[1][nr]=y; t[3][nr]=z; fin[x]=nr; }
   }
  p=u=1; st[1]=1; dist[1]=0; inf=10000000; for(i=2;i<=n;i++) dist[i]=inf;
  while(p<=u)
   { q=c[st[p]]; 
     while(q) 
	  { if(dist[t[1][q]]>dist[st[p]]+t[3][q]) {  u++; st[u]=t[1][q]; viz[t[1][q]]=1; dist[t[1][q]]=dist[st[p]]+t[3][q]; }
	    q=t[2][q];
	  }
	 p++;
   }
  for(i=2;i<=n;i++) if(viz[i]) fprintf(g,"%ld ",dist[i]); else fprintf(g,"0 ");
  fclose(g);
  return 0;
}