#include <fstream>
#include <queue>
#include <tuple>
#include <functional>
#include <vector>

constexpr auto inf = (1 << 28);

int main()
{
	std::ifstream cin("bellmanford.in");
	std::ofstream cout("dijkstra.out");

	auto n = 0;
	auto m = 0;

	cin >> n >> m;

	std::vector<std::vector<std::tuple<int, int>>> g(n + 1);

	for (auto i = 1; i <= m; i++)
	{
		auto u = 0;
		auto v = 0;
		auto c = 0;

		cin >> u >> v >> c;

		g[u].emplace_back(v, c);
	}

	std::vector<int> d(n + 1, inf);

	std::priority_queue<std::tuple<int, int>, std::vector<std::tuple<int, int>>, std::greater<std::tuple<int, int>>> q;

	q.emplace(0, 1);
	d[1] = 0;

	while (!q.empty())
	{
		const auto[c, u] = q.top();
		q.pop();

		if (c > d[u])
		{
			continue;
		}

		for (const auto&[v, cost] : g[u])
		{
			if (d[v] > d[u] + cost)
			{
				d[v] = d[u] + cost;

				q.emplace(d[v], v);
			}
		}
	}

	for (auto i = 2; i <= n; i++)
		cout << d[i] << ' ';

	return 0;
}