#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<bool> visited(Graph.size(), false);
    std::vector<int> costs(Graph.size(), inf);
    costs[startNode] = 0;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> Queue;
    Queue.push({0, startNode});
    while (!Queue.empty()) {
        auto top = Queue.top();
        int u = top.second;
        int c = top.first;
        Queue.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (auto& p : Graph[u]) {
            if (costs[p.first] > c + p.second) {
                costs[p.first] = c + p.second;
                Queue.push({costs[p.first], p.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);
    for (int i = 0; i < E; ++i) {
        int x, y, c;
        f >> x >> y >> c;
        Graph[x - 1].push_back({y - 1, c});
    }
    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;
}