#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(), std::numeric_limits<int>::max());

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

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

		for (auto neighbour : g[x]) {

			if (distance[x] + neighbour.second < distance[neighbour.first]) {
				distance[neighbour.first] = distance[x] + neighbour.second;
				PQ.push(neighbour);
			}

		}
	}

	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;
}