#include <bits/stdc++.h>

using namespace std;

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

int n, m, dp[50100], x, y, c;
priority_queue <pair <int, int> > q;
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;
	q.push({0, 1});
	while(!q.empty()){
		w = q.top();
		q.pop();
		if(-w.first > dp[w.second])
			continue;
		for(auto i : v[w.second])
			if(-w.first + i.second < dp[i.first]){
				dp[i.first] = -w.first + i.second;
				q.push({-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;
}