#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define mx INT_MAX
#define pq priority_queue

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n, m, x, y, c, dp[50100];
vector <pair <int, int> > v[50100]; 
set <pair <int, int> > heap;

int main(){
	ios_base :: sync_with_stdio(0);
	in.tie(0);
	in >> n >> m;
	for(int i = 1; i <= m; i++){
		in >> x >> y >> c;
		v[x].pb(mp(y, c));
	}
	for(int i = 1; i <= n; i++) dp[i] = mx;
	dp[1] = 0;
	pair <int, int> x = mp(0, 0);
	heap.insert(mp(0, 1));
	while(!heap.empty()){
		x = mp(heap.begin()->st, heap.begin()->nd);
		heap.erase(heap.begin());
		for(auto it : v[x.nd]){
			int nod = it.st;
			int dist = it.nd;
			if(dp[x.nd] + dist < dp[nod]){
				if(dp[nod] != mx) heap.erase(heap.find(mp(dp[nod], nod)));
				dp[nod] = dp[x.nd] + dist;
				heap.insert(mp(dp[nod], nod));
				}
		}
	}
	for(int i = 2; i <= n; i++){
		if(dp[i] == mx) out << "0 ";
		else out << dp[i] << ' ';
	}
	return 0;
}