#include <bits/stdc++.h>
using namespace std;

#define int long long

constexpr int INF = 2e18;

vector<pair<int, int>> adj[50005];

signed main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m; cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
	}

	vector<int> dist(n+1, INF);
	dist[1] = 0;

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push({0, 1});
	while (!pq.empty()) {
		auto [nAvem_nevoie, top] = pq.top();
		pq.pop();
		if (nAvem_nevoie > dist[top]) continue;
		for (auto& [vecin, weight] : adj[top]) {
			if (dist[vecin] > dist[top] + weight) {
				dist[vecin] = dist[top] + weight;
				pq.push({dist[vecin], vecin});
			}
		}
	}

	for (int i = 2; i <= n; ++i) {
		cout << dist[i] << ' ';
	}

	return 0;
}