#include <bits/stdc++.h>
using namespace std;
vector <pair <int, int> > a[50001];
int dist [50001];
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");

int main(){
	int n,m;
	in >> n >> m;
	for (int i = 1; i <= n; i++){
		dist[i] = 1e9;
	}
	for (int i = 0; i < m; i++){
		int x,y,cost;
		in >> x >> y >> cost;
		a[x].push_back({cost, y});	
	}
	set <pair <int, int> > s;
	// {dist, node} s.begin()->second;
	dist[1] = 0;
	s.insert({0, 1});
	while (!s.empty()) {
		int node = s.begin()->second;
		s.erase(s.begin());
		for (auto next: a[node]) {
			int cost = next.first;
			int next_node = next.second;
			int urmatoarea = dist[node] + cost;
			if (urmatoarea < dist[next_node]) {
				s.erase({dist[next_node], next_node});
				dist[next_node] = urmatoarea;
				s.insert({dist[next_node], next_node});
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		if (dist[i] == 1e9) {
			out << "0 ";
		}
		else {
			out << dist[i] << " ";
		}
	}
}