#include <bits/stdc++.h>

using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

int n, m, d[50001], viz[50001];
vector <pair<int,int>> graf[50001];
priority_queue <pair<int,int>> pq;

void citire() {
    int x, y, c;
    fin >> n >> m;
    for (int i = 1 ; i <= m ; i++) {
        fin >> x >> y >> c;
        graf[x].push_back({y,c});
        //graf[y].push_back({x,c});
    }
    for (int i = 2 ; i <= n ; i++){
        d[i] = -1;
    }
}

void dijkstra(){
    pair<int,int> vf;
    int nod;
    nod = 1;
    pq.push({0,1});
    d[1] = 0;
    while (!pq.empty()){
        pq.pop();
        viz[nod] = 1;
        for (pair<int,int> el: graf[nod]){
            if( ( d[nod] + el.second < d[el.first] || d[el.first] == -1) && viz[el.first] == 0 ) {
                d[el.first] = d[nod] + el.second;
                pq.push({-d[el.first],el.first});
            }
        }
        if ( viz[pq.top().second] == 1 ) continue;
        nod = pq.top().second;
    }
}

int main(){
    citire();
    dijkstra();
    for (int i = 2 ; i <= n ; i++) {
        if ( !(d[i] == -1) ) fout << d[i] << " ";
        else fout << 0 << " ";
    }
}