#include <stdio.h>
#include <vector>

#define Nmax 50005

using namespace std;

vector < pair <int, int> > A[Nmax];

long sol[Nmax], d[Nmax];
int n, m, i, a, b, c, p, u, nod, l, fiu;

void BFS(){
	
	p = 1;
	u = 1;
	d[p] = 1;
	
	while (p <= u){
		nod = d[p];
		l = (int)A[nod].size();
		
		for (i = 0 ; i < l ; i++){
			fiu = A[nod][i].first;
			d[++u] = fiu;
			sol[fiu] = min ( sol[nod] + A[nod][i].second, sol[fiu] );
		}
		
		++p;
	}
}

int main (){
	
	FILE * f = fopen ("dijkstra.in", "r");
	FILE * g = fopen ("dijkstra.out", "w");
	
	fscanf (f, "%d %d", &n, &m);
	for (i = 1 ; i <= m ; i++){
		fscanf (f, "%d %d %d", &a, &b, &c);
		A[a].push_back ( make_pair (b, c) );		
	}
	
	for (i = 2 ; i <= Nmax ; i++)
		sol[i] = 500010;
	
	BFS();
	
	for (i = 2 ; i <= n ; i++)
		fprintf (g, "%d ", sol[i]);
	
	fclose(f);
	fclose(g);
	return 0;
}