#include<stdio.h>
#define N 50000
#define oo 32000

int n,m,x,y,i,j,nod_cur,viz[N],d[N],vf,cost,c;

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

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

void bellman(int nod);

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

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

		vf = 1;

		ultim = NULL;

		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(vf);

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


		return 0;
}

void bellman(int nod)
{

	viz[nod] = 1;

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


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

	d[nod] = 0;
	while(first != NULL)
	{
		nod_cur = first->val;
		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)
				{
					viz[q->info] = 1;
					s = new nod_c;
					s->val  = q->info;
					s->next = NULL;
					last->next = s;
					last = s;
				}
			}
		first = first->next;
	}
}