#include <cstdio>
#include <vector>
using namespace std;

#define Nmax 50010
#define INF 1 << 30

void citire ();
int n, m, nod, aux, cst, fiu;
int C[Nmax], H[Nmax], poz[Nmax];
vector < pair <int, int> > V[Nmax];

void down_heap (int x) {
	
	int t, c;
	t = x; c = t << 1;
	if (c < H[0] && C[H[c + 1]] < C[H[c]]) c++;
	
	while (c <= H[0] && C[H[c]] < C[H[t]]) {
		aux = H[c];
		H[c] = H[t];
		H[t] = aux;
		
		poz[H[t]] = t;
		poz[H[c]] = c;
		
		t = c; c = t << 1;
		if (c < H[0] && C[H[c + 1]] < C[H[c]]) c++;
	}
}

void up_heap (int x) {
	
	int t, c;
	c = x; t = c >> 1;
	
	while (t && C[H[c]] < C[H[t]]) {
		aux = H[c];
		H[c] = H[t];
		H[t] = aux;
		
		poz[H[c]] = c;
		poz[H[t]] = t;
		
		c = t; t = c >> 1;
	}
}

void dijkstra () {
	
	int i;
	for (i = 2; i <= n; i++)
		C[i] = INF;
	
	H[++H[0]] = 1; poz[1] = 1;
	while (H[0]) {
		
		nod = H[1];
		H[1] = H[H[0]]; H[0]--; poz[H[1]] = 1;
		down_heap (1);
		
		for (i = 0; i < (int)V[nod].size (); i++) {
			cst = C[nod] + V[nod][i].second; fiu = V[nod][i].first;
			if (C[fiu] > cst) {
				C[fiu] = cst;
				if (!poz[fiu]) {
					H[++H[0]] = fiu; poz[H[H[0]]] = H[0];
					up_heap (H[0]);
				}
				
				else 
					up_heap (poz[fiu]);
			}
		}
	}
}

int main () {

	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	
	citire ();
	dijkstra ();
	
	for (int i = 2; i <= n; i++) {
		if (C[i] == INF) C[i] = 0;
		printf ("%d ", C[i]);
	}
	
	return 0;
}

void citire () {

	int x, y, z;
	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf ("%d %d %d", &x, &y, &z);
		V[x].push_back ( make_pair (y, z) );
	}
}