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

void citire(std::vector<std::vector<std::pair<int, int> > > &graf, int &n) {
    int m;
    int i, j, w;
    std::ifstream f("dijkstra.in");
    f >> n >> m;
    graf.resize(n);
    while (m--) {
        f >> i >> j >> w;
        graf[i - 1].emplace_back(j - 1, w);

        // daca e neorientat
        // graf[j - 1].emplace_back(i - 1, w);
    }
    f.close();
}

void dijkstra() {
    std::vector<std::vector<std::pair<int, int> > > graf;
    int n;
    citire(graf, n);

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<> > q;
    std::vector d(n, INT_MAX);
    // std::vector tata(n, -1);
    d[0] = 0;
    q.emplace(d[0], 0);

    while (!q.empty()) {
        const auto [dist, i] = q.top();
        q.pop();

        if (dist != d[i])
            continue;

        for (const auto &[j, w]: graf[i])
            if (dist + w < d[j]) {
                d[j] = dist + w;
                // tata[v] = u;
                q.emplace(d[j], j);
            }
    }

    std::ofstream g("dijkstra.out");
    for (int i = 1; i < n; ++i)
        g << (d[i] == INT_MAX ? 0 : d[i]) << " ";
    g.close();
}

int main() {
    dijkstra();
    return 0;
}