/**
 *  Worg
 */
#include <queue>
#include <vector>
#include <fstream>

const int MAX_DISTANCE = 1'000'000'000 + 1;

struct NodeDistance {
    int to;
    int distance;

    NodeDistance(const int& _to, const int& _distance) : to(_to), distance(_distance) {}

    bool operator <(const NodeDistance& other) const {
        return distance > other.distance;
    }
};

class Graph {
private:
    int num_nodes;
    std::vector<std::vector<NodeDistance>> adjacency_array;

public:
    Graph(const int& _num_nodes) : num_nodes(_num_nodes) {
        adjacency_array = std::vector<std::vector<NodeDistance>>(_num_nodes, std::vector<NodeDistance>());
    }

    void add_edge(const int& from, const int& to, const int& distance) {
        adjacency_array[from].emplace_back(to, distance);
    }

    std::vector<int> run_dijkstra(const int starting_node) {
        std::vector<int> node_distances(num_nodes, MAX_DISTANCE);
        std::priority_queue<NodeDistance> priority_queue;
        //  Initialize the algorithm using the starting node
        priority_queue.emplace(starting_node, 0);  //  Distance 0 to the starting node.

        while (!priority_queue.empty()) {
            int current_node = priority_queue.top().to;
            int current_distance = priority_queue.top().distance;
            priority_queue.pop();

            if (node_distances[current_node] == MAX_DISTANCE) {
                node_distances[current_node] = current_distance;
                for (const auto& edge : adjacency_array[current_node]) {
                    if (node_distances[edge.to] == MAX_DISTANCE) {  //  Only makes sense to push this in the priority queue if the neighbour hasn't been minimized already.
                        priority_queue.emplace(edge.to, current_distance + edge.distance);
                    }
                }
            }
        }

        return node_distances;
    }
};


int main() {
    const int STARTING_NODE = 0;

    std::ifstream fin("dijkstra.in");
    int num_nodes, num_edges;
    fin >> num_nodes >> num_edges;

    Graph graph(num_nodes);
    for (int i = 0; i < num_edges; i++) {
        int from, to, distance;
        fin >> from >> to >> distance;
        graph.add_edge(from - 1, to - 1, distance);
    }
    fin.close();

    std::vector<int> distances_from_origin = graph.run_dijkstra(STARTING_NODE);
    //  Just some problem-specific processing...
    distances_from_origin.erase(distances_from_origin.begin());
    for (auto& distance : distances_from_origin) {
        distance = (distance == MAX_DISTANCE) ? 0 : distance;
    }

    std::ofstream fout("dijkstra.out");
    for (const auto& distance : distances_from_origin) {
        fout << distance << " ";
    }
    fout.close();

    return 0;
}