#include <bits/stdc++.h>
#include <stdint.h>

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

struct connection_t {
    unsigned idx;
    unsigned dist;

    bool operator<(connection_t const& other) const {
        if (this->dist > other.dist) return true;
        if (this->dist < other.dist) return false;
        return this->idx < other.idx;
    }
};

struct node_t {
    std::vector<connection_t> connections;
};

void dijkstra(node_t* graph, unsigned* dists, unsigned nodes) {
    std::priority_queue<connection_t> queue;

    queue.push(
        (connection_t) {
            .idx = 1,
            .dist = 0
        }
    );

    while(!queue.empty()) {
        connection_t node = queue.top();
        queue.pop();
        if(dists[node.idx] > node.dist) {
            dists[node.idx] = node.dist;
            for(connection_t neighbour : graph[node.idx].connections) {
                queue.push(
                    (connection_t) {
                        .idx = neighbour.idx,
                        .dist = neighbour.dist + node.dist
                    }
                );
            }
        }
    }
}

int main()
{
    node_t graph[50001];
    unsigned dists[50001], nodes, edges;

    in >> nodes >> edges;

    {
        unsigned a, b, dist;
        for(unsigned edge = 0; edge < edges; edge += 1) {
            in >> a >> b >> dist;
            graph[a].connections.push_back(
                (connection_t) {
                    .idx = b,
                    .dist = dist,
                }
            );
        }
    }

    for(unsigned node = 1; node <= nodes; node += 1) dists[node] = UINT_MAX;

    dijkstra(graph, dists, nodes);

    for(unsigned node = 2; node <= nodes; node += 1) out << dists[node] << ' ';

    return 0;
}