#include<stdio.h>
#define N 1000
#define INF 300


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;

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 bellman()
{

	int nod_cur;

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

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

	first = new nod_c;
	first->val = 1;
	first->next = NULL;
	last = first;

	while(first != NULL)
	{
		nod_cur = first->val;

		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)
				{
					s = new nod_c;

					s->val = q->info;
					s->next = NULL;
					last->next = s;
					last = s;
					viz[q->info] = 1;
				}
			}

		first = first->next;
	}
}