#include <bits/stdc++.h>
using namespace std;
#define elem pair<int, int>

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	int n, m;
	scanf("%d %d", &n, &m);
	vector<vector<elem>> nodes(n + 1);
	while (m--) {  //  add nodes
		int a, b, lg;
		scanf("%d %d %d", &a, &b, &lg);
		nodes[a].push_back(elem(lg, b));
	}

	vector<int> minim(n + 1, -1);
	priority_queue<elem, vector<elem>, greater<elem>> coada;
	coada.push(elem(0, 1));
	minim[1] = 0;
	while (coada.size()) {  //  bfs
		elem from = coada.top();
		coada.pop();
		for (; nodes[from.second].size(); nodes[from.second].pop_back()) {
			elem act = nodes[from.second].back();
			act.first += from.first;
			if (minim[act.second] < 0 || act.first < minim[act.second]) {
				coada.push(act);
				minim[act.second] = act.first;
			}
		}
	}
	for (int i = 2; i < minim.size(); i++)  //  show
		printf("%d ", max(minim[i], 0));
	return 0;
}