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

#define Nmax 50010
#define INF 0x3f3f3f3f

int n, m, a, b, c, i, aux, N, nod, fiu, cst;
int C[Nmax], H[Nmax], poz[Nmax];
vector < pair <int, int> > V[Nmax];

void citire () {

	FILE *f = fopen ("dijkstra.in", "r");
	fscanf (f, "%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		fscanf (f, "%d %d %d", &a, &b, &c);
		V[a].push_back (make_pair (b, c));
	}
	
	fclose (f);
}

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

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

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

void afisare () {

	FILE *g = fopen ("dijkstra.out", "w");
	for (i = 2; i <= n; i++) {
		if (C[i] == INF) C[i] = 0;		
		fprintf (g, "%d ", C[i]);
	}
	
	fclose (g);
}

int main () {

	citire ();
	solve ();
	afisare ();
	
	return 0;
}