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


/* Defines */
using i32 = int32_t;
using u32 = uint32_t;

#define size_t u32
// Smart

using edge_t = std::pair<size_t, u32>;

constexpr size_t MAX_NODES = 50000;

constexpr const char *inputFilename = "dijkstra.in";
constexpr const char *outputFilename = "dijkstra.out";


/* Funtion definitions */
void readInput();
std::vector<u32> dijkstra(size_t start_node);
void writeSolVec(const std::vector<u32>& solution);


/* Variables */
std::array<std::vector<edge_t>, MAX_NODES> edges;
size_t nodes;


/* Funcion declarations */
std::vector<u32> dijkstra (size_t start_node) {
    using element_t = std::pair<size_t, u32>;

    constexpr u32 MAX_PATH = 2e9;

    struct min_heap_comp {
        bool operator () (const element_t &a, const element_t &b) const {
            return a.second > b.second;
        }
    };

    std::priority_queue<element_t, std::vector<element_t>, min_heap_comp> q(min_heap_comp{}, {{start_node, 0}});
    std::vector<u32> path_lengths(nodes, MAX_PATH);

    path_lengths[start_node] = 0;

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

        if (path_lengths[node] < path_length)
            continue; /* I have already checked this node in a previous iteration */

        for (auto [to, cost] : edges[node])
            if (path_lengths[to] > path_length + cost) {
                path_lengths[to] = path_length + cost;
                q.emplace(to, path_lengths[to]);
            }
    }

    std::replace(path_lengths.begin(), path_lengths.end(), MAX_PATH, static_cast<u32>(0));
    //                                                               ^ nice implicit conversion

    return path_lengths;
}

void readInput () {
    std::ifstream file(inputFilename);
    file.exceptions(file.badbit | file.eofbit | file.failbit);

    size_t edgeCount;
    file >> nodes >> edgeCount;

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

        file >> x >> y >> cost;
        -- x, -- y;

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

void writeSolVec (const std::vector<u32> &solution) {
    std::ofstream file(outputFilename);
    file.exceptions(file.badbit | file.eofbit | file.failbit);

    if (solution.empty())
        return;

    file << solution.front();

    for (auto it = solution.cbegin() + 1; it != solution.end(); ++ it)
        file << ' ' << *it;

    file << '\n';
}


int main () {
    readInput();

    std::vector<u32> solution = dijkstra(0);
    solution.erase(solution.begin() +    0);

    writeSolVec(solution);
}