#include <stdio.h>
#define dim 50100

struct nod
{
	int nr, c;
	nod *urm;
};
int n, m, d[dim], inq[dim];
nod *prim[dim];

void add(nod *&p, int nr, int c)
{
	nod *n1=new nod;
	n1->nr=nr;
	n1->c=c;
	n1->urm=p;
	p=n1;
}

void bellmanford()
{
	int c[dim], st, dr, nd, i;
	nod *cur;
	for (i=1; i<=n; i++) d[i]=1<<30, inq[i]=0;
	c[0]=1;
	d[1]=0;
	inq[1]=1;
	st=dr=0;
	while (st<=dr)
	{
		nd=c[st];
		st++;
		cur=prim[nd];
		while (cur)
		{
			if (d[cur->nr]>d[nd]+cur->c)
			{
				d[cur->nr]=d[nd]+cur->c;
				if (!inq[cur->nr])
				{
					c[++dr]=cur->nr;
					inq[cur->nr]=1;
				}
			}
			cur=cur->urm;
		}
	}
}

int main()
{
	int a, b, c, i;
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d %d\n", &n, &m);
	for (i=1; i<=m; i++) 
	{
		scanf("%d %d %d\n", &a, &b, &c);
		add(prim[a], b, c);
	}
	bellmanford();
	for (i=2; i<=n; i++) printf("%d ", d[i]);
	return 0;
}