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

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

int n, m, vizitat[50005];
vector<pair<int, int>> lista[50005];
vector<int> dist;

int main() {
    fin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int nodStart, nodFinal, cost;
        fin >> nodStart >> nodFinal >> cost;
        lista[nodStart].push_back(make_pair(cost, nodFinal));
    }

    dist.resize(n + 1, 2147483647);
    dist[1] = 0;

    set<pair<int, int>> noduriDeProcesat;
    noduriDeProcesat.insert({0, 1});

    while (!noduriDeProcesat.empty()) {
        int nodCurent = noduriDeProcesat.begin()->second;
        noduriDeProcesat.erase(noduriDeProcesat.begin());

        if (vizitat[nodCurent]) continue;
        vizitat[nodCurent] = 1;

        for (pair<int, int> arc : lista[nodCurent]) {
            int costArc = arc.first;
            int nodVecin = arc.second;

            if (dist[nodVecin] > dist[nodCurent] + costArc && !vizitat[nodVecin]) {
                dist[nodVecin] = dist[nodCurent] + costArc;
                noduriDeProcesat.insert({dist[nodVecin], nodVecin});
            }
        }
    }

    for (int i = 2; i <= n; ++i) {
        if (dist[i] != 2147483647)
            fout << dist[i] << ' ';
        else
            fout << "0 ";
    }

    return 0;
}