#include <bits/stdc++.h>

std::vector<int> Dijkstra(std::vector<std::vector<std::pair<int, int>>>& Graph, int startNode) {
    std::vector<int> dists(Graph.size(), INT_MAX);
    std::vector<bool> visited(Graph.size(), false);
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> Queue;
    dists[startNode] = 0;
    Queue.push({dists[startNode], startNode});
    while (!Queue.empty()) {
        int u = Queue.top().second;
        Queue.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (auto& neighbor : Graph[u]) {
            int v = neighbor.first;
            int cost = neighbor.second;
            if (dists[v] > dists[u] + cost) {
                dists[v] = dists[u] + cost;
                Queue.push({dists[v], v});
            }
        }
    }
    return dists;
}

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, w;
        f >> x >> y >> w;
        x--, y--;
        Graph[x].push_back({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] == INT_MAX ? 0 : res[i]) << ' ';
    }
    g.close();
    return 0;
}