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

std::vector<int> dijkstra(std::vector<std::vector<std::pair<int, int>>> &g, int node) {
	std::priority_queue<std::pair<int, int>> PQ;
	std::vector<int> distance(g.size()+1, std::numeric_limits<int>::max());

	distance[node] = 0;
	PQ.push({ distance[node],node });

	while (!PQ.empty()) {
		int x = PQ.top().second;
		PQ.pop();

		for (auto neighbour : g[x]) {
			int to = neighbour.first;
			int cost = neighbour.second;

			if (distance[x] + cost < distance[to]) {
				distance[to] = distance[x] + cost;
				PQ.push({ -distance[to],to });
			}

		}
	}

	return distance;
}

int main(void) {
	std::ifstream in("dijkstra.in");
	int n, m;
	in >> n >> m;

	std::vector<std::vector<std::pair<int, int>>> g(n);

	for (int i = 0; i < m; i++) {
		int from, to, cost;
		in >> from >> to >> cost;
		--from, --to;
		g[from].push_back({ to,cost });
	}

	in.close();

	std::ofstream out("dijkstra.out");

	auto distance = dijkstra(g, 0);

	for (int i = 1; i < n; i++) {
		if (distance[i] == std::numeric_limits<int>::max())
			out << 0 << " ";
		else out << distance[i] << " ";
	}
	out.close();

	return 0;
}