#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 50000;
const int kInf = numeric_limits<int>::max() / 2;

vector<pair<int, int> > G[kMaxN + 1];
int D[kMaxN + 1];

void dijkstra(int x)
{
	priority_queue<pair<int, int> > pQ;
	pQ.push(make_pair(0, x));
	while (!pQ.empty()) {
		int x = pQ.top().second;
		int d = -pQ.top().first;
		pQ.pop();
		if (D[x] != kInf) continue;
		D[x] = d;
		for (auto& p : G[x]) {
			int tmp = d + p.second;
			if (D[p.first] > tmp) {
				pQ.push(make_pair(-tmp, p.first));
			}
		}
	}
}

int main()
{
	freopen("dijkstra.in", "rt", stdin);
	freopen("dijkstra.out", "wt", stdout);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		G[a].push_back(make_pair(b, c));
	}
	for (int i = 1; i <= n; ++i) D[i] = kInf;
	dijkstra(1);
	for (int i = 2; i <= n; ++i) cout << (D[i] == kInf ? 0 : D[i]) << ' ';
	cout << '\n';
	return 0;
}