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

using namespace std;

void solve() {
    uint n, m;

    ifstream fin ("dijkstra.in");
    fin >> n >> m;

    vector<vector<pair<uint, uint>>> graph(n);
    for (uint i = 0; i < m; i++) {
        uint a, b, c;
        fin >> a >> b >> c;
        graph[a - 1].push_back({b - 1, c});
    }

    struct node_t {
        uint index, dist;
    };

    auto cmp_node = [](const node_t &n1, const node_t &n2) {
        return n1.dist > n2.dist;
    };

    const uint infinity = __INT_MAX__;

    vector<uint> distance(n, infinity);
    vector<bool> itsDone(n, false);
    priority_queue<node_t, vector<node_t>, decltype(cmp_node)> pq(cmp_node);
    distance[0] = 0;
    pq.push({0, 0});

    while (!pq.empty()) {
        const uint source = pq.top().index;
        pq.pop();

        if (itsDone[source])
            continue;

        itsDone[source] = true;

        for (auto [destination, length]: graph[source]) {
            const uint new_distance = length + distance[source];
            if (distance[destination] > new_distance) {
                distance[destination] = new_distance;
                pq.push({destination, new_distance});
            }
        }
    }

    ofstream fout("dijkstra.out");
    for (uint i = 1; i < distance.size(); i++) {
        const uint x = distance[i];
        fout << ((x == infinity) ? 0 : x) << " ";
    }
}

int main() {
    solve();
}