#include<bits/stdc++.h>

#define read(v) for(auto &i : v) cin >> i;

#define fl "\n"

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

void mincammino(int n, int m, vector<int> a, vector<int> b, vector<int> w, vector<long long> &d) {
	for(auto &i : d) i = -1;

	vector<vector<pll>> graph(n);

	for(int i = 0; i < m; i++) {
		graph[a[i]].push_back({b[i], w[i]});
	}

	priority_queue<pll, vector<pll>, greater<pll>> pq;
	pq.push({0, 0});

	while(!pq.empty()) {
		auto [dis, nod] = pq.top();
		pq.pop();

		if(d[nod] != -1) continue;
		
		d[nod] = dis;
		
		for(auto [node, w] : graph[nod]) {
			pq.emplace(w + dis, node);
		}
	}
}


#ifndef EVAL
int main() {
	int n, m;
	cin >> n >> m;
	vector<int> a(m), b(m), w(m);
	for(int i = 0; i < m; i++) {
		cin >> a[i] >> b[i] >> w[i];
	}
	vector<ll> d(n, 0);

	mincammino(n, m, a, b, w, d);

	for(auto &i : d) cout << i << " ";
	cout << fl;
}
#endif