#include<stdio.h>
FILE *f,*g;
int t[4][250500],viz[50500]; long a[5000][5000]; long c[50500],i,n,m,st[500000],dist[50500],y,z,nr,p,u,q,x,fin[50500],inf; 
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);
     a[x][y] = z;
   }
  p=u=1; st[1]=1; dist[1]=0; inf=10000000; for(i=2;i<=n;i++) dist[i]=inf;
  while(p<=u)
   { 
     for (q=1; q <= n; q++) 
		 if (a[st[p]][q]) //verifica daca exista muchie 
			 if(dist[q]>dist[st[p]]+a[st[p]][q]) 
				 {  u++; st[u]=q; viz[q]=1; dist[q]=dist[st[p]]+a[st[p]][q]; }
	 p++;
   }
  for(i=2;i<=n;i++) if(viz[i]) fprintf(g,"%ld ",dist[i]); else fprintf(g,"0 ");
  fclose(g);
  return 0;
}