#include<stdio.h>
#define max 50010
#define inf 2000000000
long d[max], n, m;
struct elem
{       long x, y, c;
	elem *urm;
}	*pr, *q;
FILE *f, *g;

void read()
{       long i, x, y, c;
	f=fopen("dijkstra.in", "r");
	fscanf(f, "%ld%ld", &n, &m);
	for(i=0; i<m; i++)
	{	fscanf(f, "%ld%ld%ld", &x, &y, &c);
		q=new elem;
		q->x=x; q->y=y; q->c=c;
		q->urm=pr;
		pr=q;
		if(x==1)
			d[y]=c;
	}
	fclose(f);
}

void write()
{	long i;
	g=fopen("dijkstra.out", "w");
	for(i=2; i<=n; i++)
		if(d[i]==inf)
			fprintf(g, "0 ");
		else
			fprintf(g, "%ld ", d[i]);
	fprintf(g, "\n");
	fclose(g);
}

void solve()
{       long i, c;
	for(i=2; i<=n; i++)
		if(d[i]==0)
			d[i]=inf;
	for(c=1; c==1;)
	{	c=0;
		for(q=pr; q; q=q->urm)
			if(d[q->y]>d[q->x]+q->c)
			{	d[q->y]=d[q->x]+q->c;
				c=1;
			}
	}

}

int main()
{       read();
	solve();
	write();
	return 0;
}