#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;

vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, const int source) {
	const int size = int(graph.size());
	auto distances = vector<int>(size, INF);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
	heap.push(make_pair(0, source));
	while (!heap.empty()) {
		const int u = heap.top().second;
		const int c = heap.top().first;
		heap.pop();
		if (distances[u] != INF) {
			continue;
		}
		distances[u] = c;
		for (const auto& e : graph[u]) {
			if (distances[e.first] == INF) {
				heap.push(make_pair(c + e.second, e.first));
			}
		}
	}
	return distances;
}


int main() {
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");
	int size, edges;
	in >> size >> edges;
	auto graph = vector<vector<pair<int, int>>>(size, vector<pair<int, int>>());
	for (; edges > 0; --edges) {
		int u, v, c;
		in >> u >> v >> c;
		graph[u - 1].push_back(make_pair(v - 1, c));
	}
	const auto distances = dijkstra(graph, 0);
	for (int u = 1; u < size; ++u) {
		out << (distances[u] == INF ? 0 : distances[u]) << (u < size - 1 ? " " : "\n");
	}
	in.close();
	out.close();
	return 0;
}