#include <bits/stdc++.h>
using namespace std;
vector<int> N[60000], C[60000], R;
int F[60000];
int n,l;
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);
    }

    d=1;
    int nr = -1;
    while(l--){
        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];
            }
            R.push_back(N[d][i]);
        }
        d = R[nr];
    }

    for(int i=2; i<=n; i++){
        cout << F[i] << ' ';
    }
}