#include <bits/stdc++.h>

#define inf 1 << 30

int extractMin(std::vector<int>& c, std::vector<bool>& v) {
    int node = -1;
    int min = inf;
    for (size_t i = 0; i < c.size(); i++) {
        if (!v[i] && c[i] <= min) {
            min = c[i];
            node = i;
        }
    }
    return node;
}

std::vector<int> dijkstra(std::vector<std::vector<int>>& Graph, int startNode) {
    std::vector<bool> visited(Graph.size(), false);
    std::vector<int> costs(Graph.size(), inf);

    costs[startNode] = 0;

    for (size_t i = 0; i < Graph.size(); i++) {
        int node = extractMin(costs, visited);
//        std::cout << node << '\n';
        visited[node] = true;
        for (size_t j = 0; j < Graph[node].size(); j++) {
            if (!visited[j] && Graph[node][j] && costs[node] != inf && costs[j] > costs[node] + Graph[node][j]) {
                costs[j] = costs[node] + Graph[node][j];
            }
        }
    }

    return costs;
}

int main() {
    std::ifstream f("dijkstra.in");
    int V, E;
    f >> V >> E;
    std::vector<std::vector<int>> Graph(V, std::vector<int> (V, 0));
    for (int i = 0; i < E; ++i) {
        int x, y, w;
        f >> x >> y >> w;
        Graph[--x][--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();

//    std::for_each(Graph.begin() + 1, Graph.end(), [] (std::vector<int>& line) {std::for_each(line.begin() + 1, line.end(), [] (int& w) {std::cout << w << ' ';}); std::cout << '\n';});
    return 0;
}