#include <stdio.h>
	
const int inf = 1<<30;
	
 
	
int n, m, h[50001], poz[50001], d[50001], k;
	
 
	
typedef struct nod
	
{
	
	int x, c;
	
	nod *a;
	
} *pNod;
	
pNod v[50001];
	
 
	
void citire()
	
{
	
	freopen("dijkstra.in","r",stdin);
	
	freopen("dijkstra.out","w",stdout);
	
 
	
	int i, x, y, c;
	
	pNod p;
	
 
	
	scanf("%d %d",&n,&m);
	
	for (i = 1; i <= m; i++)
	
	{
	
		scanf("%d %d %d",&x,&y,&c);
	
		p = new nod;
	
		p -> x = y;
	
		p -> c = c;
	
		p -> a = v[x];
	
		v[x] = p;
	
	}
	
}
	
 
	
void swap(int x, int y)
	
{
	
	int aux = h[x];
	
	h[x] = h[y];
	
	h[y] = aux;
	
}
	
 
	
void urc(int p)
	
{
	
	if (d[ h[p] ] < d[ h[p / 2] ] && p > 1)
	
	{
	
		poz[ h[p] ] = p / 2;
	
		poz[ h[p / 2] ] = p;
	
		swap(p, p / 2);
	
		urc(p / 2);
	
	}
	
}
	
 
	
void cobor(int p)
	
{
	
	int s, dr, max = p;
	
	s = p * 2;
	
	dr = p * 2 + 1;
	
 
	
	if (s <= k) if (d[ h[s] ] < d[ h[p] ]) max = s;
	
 
	
	if (dr <= k) if (d[ h[dr] ] < d[ h[max] ]) max = dr;
	
 
	
	if (max != p)
	
	{
	
		poz[ h[p] ] = max;
	
		poz[ h[max] ] = p;
	
		swap(p, max);
	
		cobor(max);
	
	}
	
}
	
 
	
 
	
void dijkstra()
	
{
	
	int i, min;
	
	pNod p;
	
 
	
	for (i = 2; i <= n; i++) poz[i] = -1, d[i] = inf;
	
	poz[1] = h[++k] = 1;
	
 
	
	while (k)
	
	{
	
		min = h[1];
	
		swap(1,k);
	
		poz[ h[1] ] = 1;
	
		k--;
	
 
	
		cobor(1);
	
 
	
		for (p = v[min]; p != NULL; p = p -> a)
	
			if (d[p -> x] > d[min] + p -> c)
	
			{
	
				d[p -> x] = d[min] + p -> c;
	
 
	
				if (poz[p -> x] != -1) urc(poz[p -> x]);
	
				else 
	
				{
	
					h[++k] = p -> x;
	
					poz[ h[k] ] = k;
	
					urc(k);
	
				}
	
			}
	
	}
	
}
	
 
	
int main()
	
{
	
	citire();
	
	dijkstra();
	
 
	
	int i;
	
	for (i = 2; i <= n; i++)
	
		if (d[i] == inf) printf("0 ");
	
		else printf("%d ",d[i]);
	
	printf("\n");
	
	return 0;
	
}