#include <bits/stdc++.h>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int NMAX = 50010, oo = 0x7fffffff;
const int inf = 0x3f3f3f3f;

int N, M;
int dist[NMAX];
vector<int> G[NMAX], C[NMAX];

void Dijkstra(int source, int *dist) {
	priority_queue<pair<int, int>> PQ;
	PQ.push({0, source});

	memset(dist, inf, sizeof(int) * (N + 1));
	dist[source] = 0;

	while (!PQ.empty()) {
		auto now = PQ.top();
		PQ.pop();
		if (-dist[now.second] != now.first)
			continue;
		for (int it = 0; it < int(G[now.second].size()); ++it) {
			if (dist[G[now.second][it]] > dist[now.second] + C[now.second][it]) {
				dist[G[now.second][it]] = dist[now.second] + C[now.second][it];
				PQ.push({-dist[G[now.second][it]], G[now.second][it]});
			}
		}
	}
}

int main() {
	int i, j, x, y, c, extr;

	in >> N >> M;
	while(M--) {
		in >> x >> y >> c;
		G[x].push_back(y);
		C[x].push_back(c);
	}

	Dijkstra(1, dist);

	for (i = 2; i <= N; ++i)
		out << ((dist[i] == inf) ? (0) : (dist[i])) << ' ';
	out << '\n';

	in.close(), out.close();
	return 0;
}