#include <bits/stdc++.h>

int main() {
    assert(freopen("dijkstra.in", "r", stdin));
    int V, E;
    assert(scanf("%d %d ", &V, &E) == 2);
    std::vector<std::vector<std::pair<int, int>>> G(V);
    int x, y, w;
    for (int i = 0; i < E; ++i) {
        assert(scanf("%d %d %d ", &x, &y, &w));
        G[--x].push_back({--y, w});
    }
    fclose(stdin);

//    for (int i = 0; i < V; i++) {
//        std::cout << i + 1 << '\n';
//        for (int j = 0; j < G[i].size(); j++) {
//            std::cout << G[i][j].first + 1 << ' ' << G[i][j].second << '\n';
//        }
//        std::cout << '\n';
//    }

    const int inf = 1 << 30;

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> Q;
    std::vector<int> costs(G.size(), inf);
    std::vector<bool> visited(G.size(), false);
    costs[0] = 0;

    Q.push({0, 0});

    while (!Q.empty()) {
        auto top = Q.top();
        Q.pop();
        int node = top.second;
        if (visited[node]) continue;
        visited[node] = true;
        for (auto& neighbor : G[node]) {
            if (costs[neighbor.first] > costs[node] + neighbor.second) {
                costs[neighbor.first] = costs[node] + neighbor.second;
                Q.push({costs[neighbor.first], neighbor.first});
            }
        }
    }

    assert(freopen("dijkstra.out", "w", stdout));
    for (size_t i = 1; i < costs.size(); ++i) {
        printf("%d ", costs[i] == inf ? 0 : costs[i]);
    }
    fclose(stdout);

    return 0;
}