#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
const int MX = 1e5+1, INF = 1e9;
int n, m, x, y, c;
vector<ii> adj[MX];
int dist[MX];

int main() {
	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> c;
		adj[x].push_back(ii(y, c));
	}
	for (int i = 0; i < MX; i++) {
		dist[i] = INF;
	}
	dist[1] = 0;
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	pq.push(ii(0, 1));
	while (!pq.empty()) {
		ii t = pq.top();
		pq.pop();
		int d = t.first, u = t.second;
		if (d == dist[u]) {
			for (int i = 0; i < adj[u].size(); i++) {
				int v = adj[u][i].first, ed = adj[u][i].second;
				if (d + ed < dist[v]) {
					dist[v] = d+ed;
					pq.push(ii(dist[v], v));
				}
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		cout << (dist[i] == INF ? 0 : dist[i]) << " ";
	}
	return 0;
}