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

struct Info
{
	int nod;
	int cost;
	bool operator()(const Info& a, const Info& b) { return a.cost > b.cost; }
};

std::vector<std::vector<Info> >la; // first = node  second = cost
int N, M;

void citire() {
	std::ifstream f("dijkstra.in");
	f >> N >> M;
	la.resize(N + 1);

	for (int i = 0; i < M; ++i) {
		int x, y, c;
		f >> x >> y >> c;
		la[x].push_back({ y,c });
	}
}

void sol() {
	std::vector<int> dist(N + 1, 1e9);
	std::vector<bool>used(N + 1, false);
	std::priority_queue<Info, std::vector<Info>, Info> pq;
	dist[1] = 0;
	
	pq.push({ 1, 0 });

	while (!pq.empty()) {
		int nod = pq.top().nod;

		if (used[nod])continue;
		used[nod] = true;
		pq.pop();

		for (auto vecin: la[nod]) {
			if (!used[vecin.nod] && dist[nod] + vecin.cost < dist[vecin.nod]) {
				dist[vecin.nod] = dist[nod] + vecin.cost;
				pq.push({ vecin.nod, dist[vecin.nod] });
			}
		}
	}


	std::ofstream g("dijkstra.out");
	for (int i = 2; i <= N; ++i) {
		g << (dist[i] == 1e9 ? 0 : dist[i]) << ' ';
	}
}

int main()
{
	citire();
	sol();

}