#include <bits/stdc++.h>

constexpr size_t MAXNODE = 50000;

std::array<std::vector<std::pair<int, int>>, MAXNODE> edges;
std::bitset<MAXNODE> vis;
std::array<int, MAXNODE> min_path;

void
dijkstra (int start) {
    std::priority_queue<std::pair<int, int>,
                        std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>> q;
    // price, to
    q.emplace(0, start);

    while (!q.empty()) {
        auto [price, node] = q.top();
        q.pop();

        if (vis[node])
            continue;

        vis[node] = true;
        min_path[node] = price;

        for (auto [newp, to] : edges[node])
            if (!vis[to])
                q.emplace(price + newp, to);
    }
}

int main () {
    int n, m;
    std::ifstream f("dijkstra.in");
    std::ofstream g("dijkstra.out");

    f >> n >> m;

    for (int i = 0; i != m; ++ i) {
        int from, to, price;
        f >> from >> to >> price;
        -- from, -- to;

        edges[from].emplace_back(price, to);
    }

    dijkstra(0);

    for (int i = 1; i < n; ++ i)
        g << min_path[i] << ' ';
}