#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() {
    freopen("dijkstra.in", "r", stdin);
    int V, E;
    assert(scanf("%d %d ", &V, &E) == 2);
    std::vector<std::vector<std::pair<int, int>>> Graph (V);
    int x, y, w;
    for (int i = 0; i < E; ++i) {
        assert(scanf("%d %d %d ", &x, &y, &w) == 3);
        Graph[--x].push_back(std::make_pair(--y, w));
    }
    fclose(stdin);
    auto res = dijkstra(Graph, 0);
    freopen("dijkstra.out", "w", stdout);
    for (size_t i = 1; i < res.size(); i++) {
        printf("%d ", (res[i] == inf ? 0 : res[i]));
    }
    fclose(stdout);
    return 0;
}