#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <queue>
#include <stack>
using namespace std;

int n, m;
vector<vector<pair<int, int>>> graf;

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

	cin >> n >> m;

	graf.resize(n + 1);

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

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	vector<int> dist(n + 1, 2e9);

	dist[1] = 0;
	pq.emplace(0, 1);

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

		if(d > dist[u]) continue;

		for(auto [w, v] : graf[u]) {
			if(dist[u] + w >= dist[v]) continue;

			dist[v] = dist[u] + w;
			pq.emplace(dist[v], v);
		}
	}

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

// const int NMAX = 1000;
// int n, m;
// bool vis[NMAX + 1];
// int p[NMAX + 1];
// int capacitate[NMAX + 1][NMAX + 1], flux[NMAX + 1][NMAX + 1];
// vector<vector<int>> graf(NMAX + 1);
//
// int fluxMax_Bfs(int s, int d) {
//     for (int i = 0; i <= n; i++) {
//         vis[i] = false;
//         p[i] = 0;
//     }
//
//     queue<int> q;
//     q.push(s);
//     vis[s] = true;
//     while (!q.empty()) {
//         int x = q.front();
//         q.pop();
//
//         for (auto y : graf[x]) {
//             if (vis[y] || capacitate[x][y] - flux[x][y] <= 0) continue;
//
//             vis[y] = true;
//             p[y] = x;
//             q.push(y);
//
//             if (y == d) break;
//         }
//     }
//
//     if (!vis[d]) return 0;
//
//     vector<int> path;
//     int x = d;
//     while (x != 0) {
//         path.push_back(x);
//         x = p[x];
//     }
//
//     reverse(path.begin(), path.end());
//     int bottleneck = 1e9;
//     for (int i = 0; i < path.size() - 1; i++) {
//         int x = path[i], y = path[i + 1];
//         bottleneck = min(bottleneck, capacitate[x][y] - flux[x][y]);
//     }
//     for (int i = 0; i < path.size() - 1; i++) {
//         int x = path[i], y = path[i + 1];
//         flux[x][y] += bottleneck;
//         flux[y][x] -= bottleneck;
//     }
//
//     return bottleneck;
// }
// void fluxMax() {
//     ifstream cin("maxflow.in");
//     ofstream cout("maxflow.out");
//     cin >> n >> m;
//
//     for (int i = 0; i < m; i++) {
//         int x, y, c;
//         cin >> x >> y >> c;
//
//         capacitate[x][y] = c;
//         graf[x].push_back(y);
//         graf[y].push_back(x);
//     }
//
//     int sum = 0;
//     while (true) {
//         int flux = fluxMax_Bfs(1, n);
//         if (flux == 0) break;
//
//         sum += flux;
//     }
//     cout << sum;
// }

// void topoSort() {
//     ifstream cin("sortaret.in");
//     ofstream cout("sortaret.out");
//
//     int n, m;
//     cin >> n >> m;
//
//     vector<vector<int>> graf(n + 1);
//     vector<int> grad(n + 1, 0);
//     for (int i = 0; i < m; i++) {
//         int x, y;
//         cin >> x >> y;
//
//         grad[y]++;
//         graf[x].push_back(y);
//     }
//
//     queue<int> q; // Pentru minim lexicografic trebuie priority_queue
//     for (int i = 1; i <= n; i++) {
//         if (grad[i] != 0) continue;
//         q.push(i);
//     }
//
//     vector<int> result;
//     while (!q.empty()) {
//         int x = q.front();
//         q.pop();
//
//         result.push_back(x);
//
//         for (auto y : graf[x]) {
//             grad[y]--;
//             if (grad[y] != 0) continue;
//
//             q.push(y);
//         }
//     }
//
//     for (auto x : result) {
//         cout << x << " ";
//     }
//     cout << endl;
// }