#include<bits/stdc++.h>

using namespace std;

vector<pair<int, long long>> v[50001];
bool visited[50001];
vector<long long> dist(50001);

void dijkstra(int start) {
	visited[start] = 1;
	dist[start] = 0;
	priority_queue<pair< long long , int >> pq;
	pq.push(make_pair(0, start));
	while (!pq.empty()) {
		int curent_distance = -pq.top().first;
		int node = pq.top().second;
		pq.pop();
		if (dist[node] < curent_distance) {
			continue;
		}
		for (auto&& neighbor : v[node]) {
			if (!visited[neighbor.first] || dist[neighbor.first] > dist[node] + neighbor.second) {
				dist[neighbor.first] = dist[node] + neighbor.second;
				visited[neighbor.first] = 1;
				pq.push(make_pair(-dist[neighbor.first], neighbor.first));
			}
		}
	}
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);


	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int a, b, cost;
		cin >> a >> b >> cost;
		v[a].push_back(make_pair(b, cost));
	}

	dijkstra(1);
	for (int i = 2; i <= n; ++i)
		cout << dist[i] << " ";

	return 0;
}