#include<stdio.h>
#define N 50001
#define INF 30000
#define M 55000


void bellman();

struct nod{ int info, cost;
	    nod *urm; } *prim[N],*p,*q;

struct nod_c {int val;
	      nod_c *next; } *first, *last, *s;

int d[N], viz[N], n, m, i, j, x, y, c, coada[N];

int main()
{
	freopen("dijkstra.in","r", stdin);
	freopen("dijkstra.out","w", stdout);

	scanf("%d %d", &n, &m);

	for( i = 1; i <= m; i++)
		{
		scanf("%d %d %d", &x, &y, &c);

		p = new nod;
		p->cost = c;
		p->info = y;
		p->urm  = prim[x];
		prim[x] = p;
		}

	bellman();

	for(i = 2; i <= n; i++)
		if(d[i] < INF)
			printf("%d ", d[i]);
		else
			printf("0 ");

	return 0;
}
void inc(int &x){
     if(x==M-1)x=0;
     else x++;
}
void bellman()
{

	int nod_cur,p,u;

	for(i = 1; i <= n; i++)
		d[i] = INF;

	d[1]   = 0;
	viz[1] = 1;

	coada[0] = 1;
	p=0;
	u=1;

	while(p != u)
	{
		nod_cur = coada[p];
		//viz[nod_cur] = 0;

		for(q = prim[nod_cur]; q; q = q->urm)
			if(d[nod_cur] + q->cost < d[q->info])
			{
				d[q->info] = d[nod_cur] + q->cost;
				//if(viz[q->info] == 0)
				//{
					coada[u] = q->info;
				//	viz[q->info] = 1;

					inc(u);
				//}
			}
	       inc(p);
	}
}