#include <array>
#include <fstream>
#include <queue>
#include <utility>
#include <vector>

constexpr int INF = 1000000000;

std::array<std::vector<std::pair<int, int>>, 50010> edges;

std::vector<int> dijkstra (int start, int n) {
	using q_e_t = std::pair<int, int>; // [node, cost]
	struct comp {
		bool operator() (q_e_t a, q_e_t b) {
			return a.second > b.second;
		}
	};
	std::priority_queue<q_e_t, std::vector<q_e_t>, comp> q;
	std::vector<int> result(n + 1, INF);

	result[start] = 0;

	q.emplace(start, 0);

	while (!q.empty()) {
		auto [node, dist] = q.top();
		q.pop();

		if (result[node] != dist)
			continue;

		for (auto [to, cost]: edges[node])
			if (dist + cost < result[to]) {
				result[to] = dist + cost;
				q.emplace(to, result[to]);
			}
	}

	for (auto &val: result)
		if (val == INF)
			val = 0;

	return result;
}

int main () {
	std::ifstream in("dijkstra.in");
	in.exceptions(std::ifstream::failbit);
	std::ofstream out("dijkstra.out");
	out.exceptions(std::ofstream::failbit);

	int n, m;
	in >> n >> m;

	for (int i = 0; i < m; ++ i) {
		int x, y, z;
		in >> x >> y >> z;

		edges[x].emplace_back(y, z);
	}

	const auto result = dijkstra(1, n); // n + 1 elements; [0] is to be ignored

	for (auto it = result.cbegin() + 2; it != result.cend(); ++ it)
		out << *it << ' ';
	out << '\n';
}