#include <bits/stdc++.h>

const int INF = 0x3f3f3f3f / 2;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    int n, m;
    std::cin >> n >> m;

    std::vector<std::pair<int, int>> edges[n + 1];
    for (int i = 0; i < m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        edges[u].push_back({v, w});
    }

    std::vector<int> dist(n + 1, INF);
    dist[1] = 0;
 
    std::queue<int> q;
    q.push(1);

    while(!q.empty()) { 
        int from = q.front();
        q.pop();

        for (auto [to, cost] : edges[from]) {
            if (dist[to] > dist[from] + cost) {
                dist[to] = dist[from] + cost;
                q.push(to);
            }
        }
    }

    for(int i = 2; i <= n; i++) {
        std::cout << dist[i] << " ";
    }

    return 0;
}