#include <bits/stdc++.h>
using namespace std;
 
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define cin f
#define cout g 
 
vector<vector<pair<int, int>>> adj;
vector<int> dist;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
 
int main() {
    int n, m;
    cin >> n >> m;
 
    adj.resize(n+1);
    dist.resize(n+1, INT_MAX);
 
    for (int i = 0; i < m; i++) {
        int from, to, cost;
        cin >> from >> to >> cost;
        adj[from].push_back({cost, to});
    }
 
    heap.push({0, 1});
    dist[1] = 0;
 
    while (!heap.empty()) {
        int cost = heap.top().first;
        int from = heap.top().second;
        heap.pop();
 
        for (auto neighbour : adj[from]) {
            if (cost + neighbour.first < dist[neighbour.second]) {
                dist[neighbour.second] = cost + neighbour.first;
                heap.push({cost + neighbour.first, neighbour.second});
            }
        }
    }
 
    for (int i = 2; i <= n; i++) 
        cout << dist[i] << " ";
 
    return 0;
}