#include<stdio.h>
#define Nmax 50005
#define inf 2000000000

int v[5*Nmax][3], c[Nmax], n, m, i, j, ok;

int main (){
	
	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	
	for (i = 2 ; i <= n ; i++)
		c[i] = inf;
	
	for (i = 1 ; i <= m ; i++){
		scanf ("%d %d %d", &v[i][0], &v[i][1], &v[i][2]);
		if (v[i][0] == 1)
			c[ v[i][1] ] = v[i][2];
	}
	
	while (!ok){
		
		ok = 1;
		
		for (i = 1 ; i<= m ; i++)
			if (c[ v[i][1] ] > c[ v[i][0] ] + v[i][2]){
				c[ v[i][1] ] = c[ v[i][0] ] + v[i][2];
				ok = 0;
			}
	}
	
	for (i = 2 ; i <= n ; i++)
		if (c[i] < inf)
			printf("%d ", c[i]);
		else 
			printf("0");

	return 0;
}