#include <cstdio>
#include <algorithm>
#include <list>

using namespace std;

#define NMAX 50050
#define INF 1 << 30

int C[NMAX], H[NMAX], poz[NMAX], N, n;
list < pair <int, int> > G[NMAX];

void citire (), dijkstra (), up_heap (int), down_heap (int), afisare ();

int main () {
	
	citire ();
	
	dijkstra ();
	
	afisare ();
	
	return 0;
}

void citire () {
	
	freopen ("dijkstra.in", "r", stdin);
	
	int m, i, x, y, c;
	
	scanf ("%d %d", &n, &m);
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d %d", &x, &y, &c);
		G[x].push_back (make_pair (y, c));
	}
}

void up_heap (int k) {
	
	int c = k, t = c >> 1;
	
	while (t > 0 && C[H[t]] > C[H[c]]) {
		swap (H[c], H[t]);
		poz[H[c]] = c, poz[H[t]] = t;
		
		c = t, t = c >> 1;
	}
}

void down_heap (int k) {
	
	int t = k, c = t << 1;
	
	if (c < N && C[H[c+1]] < C[H[c]]) c++;
	
	while (c <= N && C[H[t]] > C[H[c]]) {
		swap (H[c], H[t]);
		poz[H[c]] = c, poz[H[t]] = t;
		
		t = c, c = t << 1;
		if (c < N && C[H[c+1]] < C[H[c]]) c++;
	}
}

void dijkstra () {
	
	int nod, fiu, cst, i;
	list < pair <int, int> >::iterator it;
	
	for (i = 2; i <= n; i++) C[i] = INF;
	
	N++;
	H[1] = 1, poz[1] = 1;
	
	while (N) {
		nod = H[1];
		H[1] = H[N], poz[H[1]] = 1, N--;
		down_heap (1);
		
		for (it = G[nod].begin (); it != G[nod].end (); it++) {
			fiu = it -> first, cst = it -> second;
			
			if (C[nod] + cst < C[fiu]) {
				C[fiu] = C[nod] + cst;
				
				if (!poz[fiu]) {
					N++, H[N] = fiu, poz[fiu] = N;
					up_heap (N);
				}
				else
					up_heap (poz[fiu]);
			}
		}
	}
}

void afisare () {
	
	freopen ("dijkstra.out", "w", stdout);
	
	for (int i = 2; i <= n; i++)
		if (C[i] != INF) printf ("%d ", C[i]);
		else printf ("0 ");
}