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

const long long INF = 1e18;

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

    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    int N, M;
    fin >> N >> M;

    vector<vector<pair<int, int>>> graf(N + 1);

    for (int i = 0; i < M; i++) {
        int A, B, C;
        fin >> 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, nod)

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

    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});
            }
        }
    }

    for (int i = 2; i <= N; i++) {
        if (dist[i] == INF) fout << 0;
        else fout << dist[i];

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

    return 0;
}