#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#define node first
#define weight second
#define nmax 50001
#define inf (1<<30)
using namespace std;

void get_data (int &n_nodes, int &n_edges, int dist[nmax], vector <pair <int, int> > edges [nmax]){
    ifstream fin ("dijkstra.in");
    fin >> n_nodes >> n_edges;
    for (int i = 2; i <= n_nodes; i++)
        dist[i] = inf;
    dist[1] = 0;
    for (int i = 1; i <= n_edges; i++){
        int node_1, node_2, weight;
        fin >> node_1 >> node_2 >> weight;
        edges[node_1].push_back (make_pair (node_2, weight));
    }
}

void dijkstra (int n_nodes, int dist[nmax], vector <pair <int, int> > edges [nmax]){
    set <pair <int, int> > s;
    s.insert (make_pair (0, 1));
    while (!s.empty()){
        int current_node = s.begin()-> second;
        int current_node_value = s.begin() -> first;
        s.erase (s.begin());
        for (auto x : edges[current_node])
            if (dist[x.node] > x.weight + current_node_value){
                dist[x.node] = x.weight + current_node_value;
                s.insert (make_pair (dist[x.node], x.node));
            }
    }
}

void print_data (int n_nodes, int dist[nmax]){
    ofstream fout ("dijkstra.out");
    for (int i = 2; i <= n_nodes; i++)
        if (dist[i] == inf)
            fout << -1 << " ";
        else
            fout << dist[i] << " ";
}

int main(){
    int n_nodes, n_edges;
    int dist [nmax];
    vector <pair <int, int> > edges [nmax];
    get_data (n_nodes, n_edges, dist, edges);
    dijkstra (n_nodes, dist, edges);
    print_data (n_nodes, dist);
    return 0;
}