#include <stdio.h>

const int inf = 1<<30;

int n, m, k, d[50001], h[50001], poz[50001];

typedef struct nod
{
	int x, c;
	nod *a;
} *pNod;
pNod v[50001];

void add(pNod &p, int x, int c)
{
	pNod q = new nod;
	q -> x = x;
	q -> c = c;
	q -> a = p;
	p = q;
}

void citire()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);

	int i, x, y, c;
	scanf("%d %d",&n,&m);

	for (i = 1; i <= m; i++)
	{
		scanf("%d %d %d",&x,&y,&c);
		add(v[x],y,c);
	}
}

void swap(int x, int y) { int t = h[x]; h[x] = h[y]; h[y] = t; }

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 max, st, dr;
	st = p * 2;
	dr = st + 1;
	max = p;

	if (st <= k) if(d[ h[p] ] > d[ h[st] ]) max = st;

	if (dr <= k) if(d[ h[max] ] > d[ h[dr] ]) max = dr;

	if (max != p)
	{
		poz[ h[p] ] = max;
		poz[ d[max] ] = p;
		swap(p,max);

		cobor(max);
	}
}

void dijkstra()
{
	int min, i;
	pNod p;

	h[++k] = poz[1] = 1;
	for (i = 2; i <= n; i++) poz[i] = -1, d[i] = inf;
	
	while (k)
	{
		min = h[1];
		swap(1,k); k--;
		poz[ h[1] ] = 1;
		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) { h[++k] = p -> x; poz[p -> x] = k; urc(k); }
				else urc(poz[p -> x]);
			}
	}
}

int main()
{
	int i;
	citire();
	dijkstra();
	for (i = 2; i <= n; i++) printf("%d ",d[i] != inf ? d[i] : 0);
	printf("\n");
	return 0;
}