#include <bits/stdc++.h>

using namespace std;

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

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

int main() {
	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		in >> x >> y >> c;
		v[x].push_back({c, y});
	}
	
	for (int i = 1; i <= n; i++)
		d[i] = 2e9;
	
	d[1] = 0;
	h.insert({0, 1});
	while (!h.empty()) {
		auto w = *h.begin();
		h.erase(h.begin());
		
		for (auto it : v[w.second]) {
			int dist = d[w.second] + it.first;
			if (dist < d[it.second]) {
				if (d[it.second] != 2e9)
					h.erase(h.find({d[it.second], it.second}));
				
				d[it.second] = dist;
				h.insert({dist, it.second});
			}
		}
	}
	
	for (int i = 2; i <= n; i++)
		out << (d[i] == 2e9 ? 0 : d[i]) << ' ';
	return 0;
}