#include <bits/stdc++.h>
using namespace std;

#define INF 1e9

vector<int> dijkstra(int source, const vector<vector<pair<int, int>>>& adj) {
	priority_queue<pair<int, int>> pq;
	pq.push({0, source});

	vector<bool> visited(adj.size(), 0);
	vector<int> dist(adj.size(), INF);
	dist[source] = 0;

	while (!pq.empty()) {
		int current = pq.top().second;
		pq.pop();

		if (visited[current])
			continue;

		visited[current] = 1;

		for (const auto& [neigh, cost] : adj[current])
			if (dist[neigh] > dist[current] + cost) {
				dist[neigh] = dist[current] + cost;
				pq.push({-dist[neigh], neigh});
			}
	}

	return dist;
}
int main() {
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");

	int n, m;
	fin >> n >> m;

	vector<vector<pair<int, int>>> adj(n + 1);
	for (int i = 1, x, y, c; i <= m; ++i) {
		fin >> x >> y >> c;
		adj[x].push_back({y, c});
	}

	vector<int> dist = dijkstra(1, adj);
	for (int i = 2; i <= n; ++i)
		fout << (dist[i] == INF ? 0 : dist[i]) << ' ';
	fout << '\n';
}