#include <bits/stdc++.h>

#define inf 1 << 30

std::vector<int> dijkstra(std::vector<std::vector<std::pair<int, int>>>& Graph, int startNode) {
    std::vector<int> costs(Graph.size(), inf);
    costs[0] = 0;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> queue;
    // pair : (cost, node)
    queue.push(std::make_pair(0, 0));
    while (!queue.empty()) {
        auto top = queue.top();
        queue.pop();
        int cost = top.first;
        int node = top.second;
        for (auto& neighbor : Graph[node]) {
            if (costs[neighbor.first] > cost + neighbor.second) {
                costs[neighbor.first] = cost + neighbor.second;
                queue.push({costs[neighbor.first], neighbor.first});
            }
        }
    }
    return costs;
}

int main() {
    std::ifstream f("dijkstra.in");
    int V, E;
    f >> V >> E;
    std::vector<std::vector<std::pair<int, int>>> Graph (V);
    int x, y, w;
    for (int i = 0; i < E; ++i) {
        f >> x >> y >> w;
        Graph[--x].push_back(std::make_pair(--y, w));
    }
    f.close();
    auto res = dijkstra(Graph, 0);
    std::ofstream g("dijkstra.out");
    for (size_t i = 1; i < res.size(); i++) {
        g << (res[i] == inf ? 0 : res[i]) << ' ';
    }
    g.close();
    return 0;
}