#include <bits/stdc++.h>

using namespace std;

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

int main() {
	int n, m;
	f >> n >> m;
	vector < vector <pair <int, int> > > adj(n);
	for (int i = 0; i < m; ++i) {
		int u, v, cost;
		f >> u >> v >> cost;
		--u; --v;
		adj[u].push_back({v, cost});
	}
	set < pair <int, int> > s;
	s.insert({0, 0});
	vector <int> dist(n);
	for (int i = 0; i < n; ++i) {
		dist[i] = -1;
	}
	while (!s.empty()) {
		int node = (*s.begin()).first;
		int cost = (*s.begin()).second;
		s.erase(s.begin());

		if (dist[node] == -1) {
            dist[node] = cost;
            for (auto &p : adj[node]) {
                if (dist[p.first] == -1) {
                    s.insert({p.first, cost + p.second});
                }
            }
		}
	}
	for (int i = 1; i < n; ++i) {
		if (dist[i] == -1) {
			g << "0 ";
		} else {
			g << dist[i] << ' ';
		}
	}
	f.close();
	g.close();
	return 0;
}