#include <bits/stdc++.h>

using namespace std;

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

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

void dij(){
	for(int i = 1; i <= n; i++)
		dp[i] = 2e9;
	dp[1] = 0;
	h.insert({0, 1});
	while(!h.empty()){
		w = *h.begin();
		h.erase(h.begin());
		for(auto i : v[w.second])
			if(w.first + i.second < dp[i.first]){
				if(dp[i.first] != 2e9)
					h.erase(h.find({dp[i.first], i.first}));
				dp[i.first] = w.first + i.second;
				h.insert({dp[i.first], i.first});
			}
	}
}

int main(){
	in >> n >> m;
	while(in >> x >> y >> c)
		v[x].push_back({y, c});
	dij();
	for(int i = 2; i <= n; i++)
		out << (dp[i] == 2e9 ? 0 : dp[i]) << ' ';
	return 0;
}