#include <bits/stdc++.h>
#define fx first
#define sx second
#define pb push_back
typedef long long ll;
const int Max = 50006;
const int Inf = 2e9;
const int MOD = 666013;
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out"); 

int n, m, x, y, z, viz[Max], dist[Max];
vector <pair <int,int> > v[Max]; // first - node, second - edge value

void dijkstra () {
	dist[1] = 0;
	for (int i=2; i<=n; i++) dist[i] = Inf;
	priority_queue < pair<int,int> > q;
	q.push({0, 1});
	while (q.size()) {
		int node = q.top().sx;
		q.pop();
		if (viz[node]) continue;
		for (int i=0; i<v[node].size(); i++) {
			int next = v[node][i].fx, w = v[node][i].sx;
			if (dist[node] + w < dist[next]) {
				dist[next] = dist[node] + w;
				q.push({-dist[next], next});
			}
		}
		viz[node] = 1;
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	in >> n >> m;
	while (m--) {
		in >> x >> y >> z;
		v[x].pb({y, z});
	}
	dijkstra();
	for (int i=2; i<=n; i++) {
		if (dist[i] == Inf) out << "0 ";
		else out << dist[i] << " ";
	}
	return 0;
}