#include <iostream>
#include <vector>
#include <set>
#define MAXN 50100
#define INF 1000000000

using namespace std;

int n,m,d[MAXN];
vector<int> no[MAXN];
vector<int> co[MAXN];
set< pair<int, int> > t;

int main () {
	int i,a,b,c,nod,cost;
	
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	
	for (i=0; i<m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		no[a].push_back(b);
		co[a].push_back(c);
	}
	
	fill(d, d+MAXN, INF);
	
	t.insert( make_pair(1, 0) );
	
	while (t.size()) {
		nod = (*t.begin()).first;
		cost = (*t.begin()).second;
		t.erase(*t.begin());
		for (i=0; i<no[nod].size(); i++) {
			if (d[no[nod][i]] > cost + co[nod][i]) {
				d[no[nod][i]] = cost + co[nod][i];
				t.insert(make_pair(no[nod][i], d[no[nod][i]]));
			}
		}
	}
	
	for (i=2; i<=n; i++) {
		printf("%d ", (d[i] == INF) ? 0 : d[i]);
	}
	
	return 0;
}