#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

/// implementare cu min heap, complexitate O((|V| + |E|)log|V|)

const int INF = 2100000000;

int n, m;
vector <pair <int, int>> * lv;

int * d;

int q_dim;
int * q;
int * q_pos;

int pop(){

    swap(q_pos[q[1]], q_pos[q[q_dim]]);
    swap(q[1], q[q_dim]);

    bool ok = 0;

    int pos = 1;
    while(!ok)

        if(pos * 2 > q_dim && pos * 2 + 1 > q_dim)

            ok = true;

        else if(pos * 2 > q_dim){

            if(d[q[pos * 2 + 1]] > d[q[pos]])

                ok = true;

            else{

                swap(q_pos[q[pos * 2 + 1]], q_pos[q[pos]]);
                swap(q[pos * 2 + 1], q[pos]);

                pos *= 2;
                pos += 1;
            }
        }
        else if(pos * 2 + 1 > q_dim){

            if(d[q[pos * 2]] > d[q[pos]])

                ok = true;

            else{

                swap(q_pos[q[pos * 2]], q_pos[q[pos]]);
                swap(q[pos * 2], q[pos]);

                pos *= 2;
            }
        }
        else{

            if(d[q[pos]] < d[q[pos * 2]] && d[q[pos]] < d[q[pos * 2 + 1]])

                ok = true;

            else if(d[q[pos * 2]] < d[q[pos * 2 + 1]]){

                swap(q_pos[q[pos * 2]], q_pos[q[pos]]);
                swap(q[pos * 2], q[pos]);

                pos *= 2;
            }
            else{

                swap(q_pos[q[pos * 2 + 1]], q_pos[q[pos]]);
                swap(q[pos * 2 + 1], q[pos]);

                pos *= 2;
                pos += 1;
            }
        }

    q_dim -= 1;
    return q[q_dim + 1];
}

void update(int node){

    int pos = q_pos[node];

    bool ok = 0;

    while(!ok)

        if(pos / 2 == 0 || d[q[pos]] > d[q[pos / 2]])

            ok = true;
        else{

            swap(q_pos[q[pos]], q_pos[q[pos / 2]]);
            swap(q[pos], q[pos / 2]);

            pos /= 2;
        }
}

void spf(){

    while(q_dim){

        int current_node = pop();

        for(int i = 0; i < lv[current_node].size(); i++){

            int next_node = lv[current_node][i].first;
            int new_dist = d[current_node] + lv[current_node][i].second;

            if(new_dist < d[next_node]){

                d[next_node] = new_dist;
                update(next_node);
            }
        }
    }
}

int main(){

    f >> n >> m;

    lv = new vector <pair <int, int>> [n + 1];

    d = new int [n + 1];

    q_pos = new int [n + 1];
    q = new int [n + 1];

    q_dim = n;

    for(int i = 1; i <= n; i++){

        d[i] = INF;

        q[i] = i;
        q_pos[i] = i;
    }
    d[1] = 0;

    int x, y, c;
    for(int i = 0; i < m ; i++){

        f >> x >> y >> c;

        lv[x].push_back(make_pair(y, c));
    }

    spf();

    for(int i = 2; i <= n; i++)
        if(d[i] == INF)
            g << 0 << " ";
        else
            g << d[i] << " ";

    return 0;
}