#include <algorithm>
#include <ctime>
#include <vector>
#include <iostream>
#include <fstream>
#include <map>
#include <set>
#include <cmath>
#include <unordered_map>
#include <iomanip>
#include <queue>
#include <tuple>

using namespace std;

bool visited[50001];
int dist[50001];
vector<tuple<int, int>> graf[50001];

int main() {
	ifstream cin("dijkstra.in");
	ofstream cout("dijkstra.out");

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		graf[a].emplace_back(b, w);
	}

	for (int i = 0; i <= n; i++) dist[i] = 1e9;

	priority_queue<tuple<int, int>, vector<tuple<int, int>>, greater<>> pq;
	pq.emplace(0, 1); // start at node 1 with distance 0

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

		if (visited[nod]) continue;
		visited[nod] = true;

		for (const auto& [vecin, w] : graf[nod]) {
			if (d + w >= dist[vecin]) continue;
			dist[vecin] = d + w;
			pq.emplace(dist[vecin], vecin);
		}
	}

	for (int i = 2; i <= n; i++) {
		if (dist[i] >= 1e9) cout << "0 ";
		else cout << dist[i] << " ";
	}
	cout << endl;
}