#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;
}