#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
const int INF = (1 << 30);
using namespace std;
using PI = pair<int, int>;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n, m, d[50005];
vector<pair<int, int>>a[50005];
priority_queue<PI, vector<PI>, greater<PI>>coada;
void citire() {
	in >> n >> m;
	for (int i = 1; i <= n; i++) d[i] = INF;
	for (int i = 0; i < m; i++) {
		int x, y, z;
		in >> x >> y >> z;
		a[x].push_back(make_pair(y, z));
	}
}
void dijkstra(int nod) {
	d[nod] = 0;
	coada.push(make_pair(0, nod));
	while (!coada.empty()) {
		int x = coada.top().first;
		int y = coada.top().second;
		coada.pop();
		if (x > d[y]) continue;
		for (auto& q : a[y]) {
			int nodnou = q.first;
			int costnou = q.second;
			if (d[nodnou] > d[y] + costnou) {
				d[nodnou] = d[y] + costnou;
				coada.push(make_pair(d[costnou], nodnou));
			}
		}
	}
}
void afis() {
	for (int i = 2; i <= n; i++)
		if (d[i] != INF) out << d[i] << " ";
		else out << 0 << " ";
}
/*
* 5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6
*/
int main() {
	citire();
	dijkstra(1);
	afis();
}