#include<stdio.h>
#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define INF 1<<30

FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");
struct muchie
{
long sursa;
long dest;
long dist;
}e[250005];
long d[50005];
long n,m;

int main()
{
 long x,y,i;
 long c;
 fscanf(fin,"%ld %ld",&n,&m);
 for(i=1;i<=m;i++)
 {
	fscanf(fin,"%ld %ld %ld",&x,&y,&c);
	e[i].sursa=x;
	e[i].dest=y;
	e[i].dist=c;
	if(x==1)
		d[y]=c;
 }
 fclose(fin);
 for(i=2;i<=n;i++)
	if(d[i]==0)
		d[i]=INF;
 for(c=1;c==1;)
 {
	c=0;
	for(i=1;i<=m;i++)
		if(d[e[i].dest]>d[e[i].sursa]+e[i].dist)
		{
			d[e[i].dest]=d[e[i].sursa]+e[i].dist;
			c=1;
		}
 }
 for(i=2;i<=n;i++)
	if(d[i]==INF)
		fprintf(fout,"0 ");
	else
		fprintf(fout,"%ld ",d[i]);
 fclose(fout);
 return 0;
}