#include <iostream>
#include <fstream>
#include <limits>
#include <vector>
#include <queue>

const int INF = 2000000000;
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int main() {

    int n, m, x, y, cost;
    f >> n >> m;
    vector<vector<pair<int,int>>> L(n + 1);
    priority_queue<pair<int, int>> PQ;

    vector<int> d(L.size(), INF), viz(n + 1, 0);
    for (int i = 0; i < m; i++) {
        f >> x >> y >> cost;
        L[x].push_back({y,cost});
    }
    d[1]=0;
    PQ.push({-d[1], 1});
    while (!PQ.empty()) {
        int nod = PQ.top().second;
        PQ.pop();
        if (viz[nod]) {
            continue;
        }
        viz[nod] = 1;
        for (auto x : L[nod]) {
            int vecin = x.first;
            int cost = x.second;
            if (d[vecin] > d[nod] + cost) {
                d[vecin] = d[nod] + cost;
                PQ.push({-d[vecin], vecin});
            }
        }
    }
    for (int i = 2; i<= n; i++) {
        if (d[i] == INF) g << "0 ";
        else g << d[i] << " ";
    }
    return 0;
}