#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());
	std::vector<bool> inQueue(g.size(),false);

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

	while (!PQ.empty()) {
		int x = PQ.top().first;
		PQ.pop();
		inQueue[x] = false;

		for (auto neighbour : g[x]) {

			if (distance[x] + neighbour.second < distance[neighbour.first]){
				distance[neighbour.first] = distance[x] + neighbour.second;
				if (!inQueue[neighbour.first]) {
					inQueue[neighbour.first] = true;
					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 });
		g[to].push_back({ from,cost });
	}

	in.close();

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

	auto distance = dijkstra(g, 0);

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

	return 0;
}