#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 1;
int n, m;
vector<pair<int, int>> liste[N];
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int main() {

	fin.tie(0)->sync_with_stdio(0);
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, c;
		fin >> u >> v >> c;
		liste[u].push_back({v, c});
	}
	queue<int> q;
	vector<int> viz(N, 1e9 + 1);
	q.push(1);
	viz[1] = 1;
	while (!q.empty()) {
		int nod = q.front();
		q.pop();
		for (auto i : liste[nod]) {
			if (viz[i.first] > viz[nod] + i.second) {
				viz[i.first] = viz[nod] + i.second;
				q.push(i.first);
			}
		}
	}

	for (int i = 2; i <= n; i++) {
		fout << viz[i] - 1<< " ";
	}
}