#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long

using namespace std;

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

int n, m, x, y, c, dp[50100];
vector <pair <int, int> > v[50100];
priority_queue <pair <int, int> > q;

int main() {
	in >> n >> m;
	while (m--) {
		in >> x >> y >> c;
		v[x].push_back({c, y});
	}
	memset(dp, 0x3f3f3f3f, sizeof dp);
	dp[1] = 0;
	q.push({0, 1});
	while (q.size()) {
		auto nod = q.top();
		q.pop();
		if (-nod.fi > dp[nod.se])
			continue;
		for (auto x : v[nod.se])
			if (-nod.fi + x.fi < dp[x.se]) {
				dp[x.se] = -nod.fi + x.fi;
				q.push({-dp[x.se], x.se});
			}
	}
	for (int i = 2; i <= n; i++)
		out << (dp[i] != 0x3f3f3f3f ? dp[i] : 0) << ' ';
	return 0;
}