#include <algorithm>
#include <array>
#include <cstdint>
#include <fstream>
#include <queue>
#include <utility>
#include <vector>

using u32 = uint32_t;

constexpr size_t MAX_NODES = 50000;
constexpr u32 INF_PATH = 0x7fffffff;

std::array<std::vector<std::pair<size_t, u32>>, MAX_NODES> edges;
size_t nodes;


std::vector<u32> dij (size_t start) {
    std::vector<u32> result(nodes, INF_PATH);

    result[start] = 0;

    using heapValueT = std::pair<size_t, u32>;
    struct minHeapComp {
        bool operator() (heapValueT a, heapValueT b) const {
            return a.second > b.second;
        }
    };
    std::priority_queue<heapValueT,
                        std::vector<heapValueT>,
                        minHeapComp> q;

    q.emplace(start, 0);

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

        if (pathLength > result[node])
            continue;

        for (auto [toNode, cost]: edges[node])
            if (result[toNode] > pathLength + cost) {
                result[toNode] = pathLength + cost;
                q.emplace(toNode, result[toNode]);
            }
    }

    std::replace(result.begin(), result.end(), INF_PATH, 0u);

    return result;
}


int main () {
    std::ifstream in("dijkstra.in");
    std::ofstream out("dijkstra.out");

    u32 edgeCount;
    in >> nodes >> edgeCount;

    for (u32 i = 0; i != edgeCount; ++ i) {
        size_t x, y;
        u32 z;

        in >> x >> y >> z;
        -- x, -- y;

        edges[x].emplace_back(y, z);
    }

    auto result = dij(0);
    result.erase(result.begin());

    for (auto val: result)
        out << val << ' ';
}