#include <iostream>
#include <set>
#include <fstream>
#include <vector>
#define inf (1<<30)
#define nmax 50005
using namespace std;

struct graph_content{
    vector <pair <int, int> > content[nmax];
    int shortest_path[nmax];
    int number_of_nodes;
    int number_of_edges;
};

void read_graph (graph_content &graph){
    ifstream fin ("dijkstra.in");
    fin >> graph.number_of_nodes >> graph.number_of_edges;
    for (int i = 1; i <= graph.number_of_edges; i++){
        int node1, node2, distance;
        fin >> node1 >> node2 >> distance;
        graph.content[node1].push_back (make_pair (node2, distance));
    }
    for (int i = 2; i <= graph.number_of_nodes; i++)
        graph.shortest_path[i] = inf;
    graph.shortest_path[1] = 0;
}

void dijkstra (graph_content &graph){
    set <pair <int, int> > distances;
    distances.insert (make_pair (0, 1));
    while (!distances.empty ()){
        int current_node = distances.begin () -> second;
        int node_distance = distances.begin () -> first;
        distances.erase (*distances. begin ());
        for (auto neigh : graph.content[current_node])
            if (graph.shortest_path[neigh.first] > node_distance + neigh.second){
                graph.shortest_path[neigh.first] = node_distance + neigh.second;
                distances.insert (make_pair (graph.shortest_path[neigh.first], neigh.first));
            }
    }
}

void print_path (graph_content graph){
    ofstream fout ("dijkstra.out");
    for (int i = 2; i <= graph.number_of_nodes; i++)
        if (graph.shortest_path[i] == inf)
            fout << 0 << " ";
        else
            fout << graph.shortest_path[i] << " ";
}

int main(){
    graph_content graph;
    read_graph (graph);
    dijkstra (graph);
    print_path (graph);
    return 0;
}