#include <bits/stdc++.h>
using namespace std;
vector<int> N[300000], C[300000], R;
int F[300000], D[20000];
int n,l,op;
int main(){
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin >> n >> l;
    int d, p, c;
    for(int i=0; i<l; i++){
        cin >> d >> p >> c;
        N[d].push_back(p);
        C[d].push_back(c);
        if(!D[d]){
            op++;
            D[d]=1;
        }
    }

    d=1;
    int nr = -1;
    while(op--){
        nr++;
        for(int i=0; i<N[d].size(); i++){
            // cout << N[d][i] << ' ' << F[N[d][i]] << endl;
            if(F[N[d][i]] == 0 || F[N[d][i]] > (C[d][i] + F[d])){
                F[N[d][i]] = C[d][i] + F[d];
            }
            if(D[N[d][i]]){
                R.push_back(N[d][i]);
                D[N[d][i]] = 0;
            }
        }
        d = R[nr];
    }

    // for(int i=0; i<=nr; i++){
    //     cout << R[i] << endl;
    // }
    for(int i=2; i<=n; i++){
        cout << F[i] << ' ';
    }
}