#include <cstdio>

#define Nmax 1010
#define INF 1 << 30

int n, m, S;
int a[Nmax][Nmax], C[Nmax], viz[Nmax], T[Nmax];
void citire (), afisare ();

void dijkstra () {
	
	int i, j, nod, cnod;
	
	for (i = 1; i <= n; i++)
		C[i] = INF;
	C[S] = 0;
	
	for (i = 1; i <= n; i++) {
		
		cnod = INF;
		for (j = 1; j <= n; j++) 
			if (C[j] < cnod && viz[j] == 0) {
				cnod = C[j];
				nod = j;
			}
		
		for (j = 1; j <= n; j++) 
			if (a[nod][j] != INF && C[nod] + a[nod][j] < C[j]) {
				C[j] = C[nod] + a[nod][j];
				T[j] = nod;
			}
		
		viz[nod] = 1;
	}
}

int main () {

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

	return 0;
}

void citire () {

	int x, y, z, i, j;
	
	S = 1;
	
	scanf ("%d %d", &n, &m);
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			a[i][j] = INF;
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d %d", &x, &y, &z);
		a[x][y] = z;
	}
}

void drum (int nod) {
	
	if (nod != S) {
		printf ("%d ", nod);
		return ;
	}
	
	drum (T[nod]);
	printf ("%d ", nod);
}

void afisare () {

	int i;
	for (i = 2; i <= n; i++)
		printf ("%d ", C[i]);
	printf ("\n");
	
	/*drumurile
	for (i = 2; i <= n; i++) {
		drum (i);
		printf ("\n");
	}*/
}