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

int main() {
    ios::sync_with_stdio(false);

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

    int n, m;
    fin >> n >> m;

    vector<vector<pair<int, int>>> destinations(n, vector<pair<int, int>>());

    for (int i = 0; i < m; i++) {
        int src, dst, cost;
        fin >> src >> dst >> cost;

        src--; dst--;

        destinations[src].push_back({dst, cost});
    }

    vector<int> dist(n, INT_MAX);
    dist[0] = 0;

    priority_queue<pair<int, int>> q;
    q.push({0, 0});

    while (!q.empty()) {
        int node = q.top().second;
        q.pop();

        for (const auto &[dst, cost] : destinations[node]) {
            if (dist[dst] > dist[node] + cost) {
                dist[dst] = dist[node] + cost;

                q.push({-dist[dst], dst});
            }
        }
    }

    for (int i = 1; i < n; i++) {
        if (i != 1) {
            fout << ' ';
        }
        fout << dist[i];
    }
    fout << '\n';

    return 0;
}