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

const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<pair<int, int>>> graf(N + 1); 
    // graf[u] = lista de (v, cost)

    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        graf[A].push_back({B, C});
    }

    vector<long long> dist(N + 1, INF);
    vector<bool> visited(N + 1, false);

    priority_queue<pair<long long, int>> pq;  
    // (dist negativa, nod)

    dist[1] = 0;
    pq.push({0, 1}); // -0 = 0

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

        long long d = -dist_neg;

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

        for (auto [vecin, cost] : graf[nod]) {
            if (!visited[vecin] && d + cost < dist[vecin]) {
                dist[vecin] = d + cost;
                pq.push({-dist[vecin], vecin});
            }
        }
    }

    // Afișare: dacă nu există drum → 0
    for (int i = 2; i <= N; i++) {
        if (dist[i] == INF) cout << 0;
        else cout << dist[i];

        if (i != N) cout << " ";
    }

    return 0;
}