#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> V[51000], C[52000];
ll N[51000], Z[51000];
ll l, n, gasite;

set< pair<int,int> > S;

int main(){
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin >> n >> l;
    int d, p, c;
    while(l--){
        cin >> d >> p >> c;
        V[d].push_back(p);
        C[d].push_back(c);
    }
    for(int i=1; i<=n; i++){
        N[i] = 1e9;
    }
    d = 1;
    N[d] = 0;
    ll n1 = n;
    while(n1--){
        for(int i=0; i<V[d].size(); i++){
            int y = V[d][i];
            if(N[d] + C[d][i] < N[y]){
                S.erase(S.find({N[y],y}));
                N[y] = N[d] + C[d][i];
                S.insert({N[y], y});
            }
        }
        
        d = S.begin()->second;
        S.erase(S.begin());
        Z[d] = 1;
    }

    for(int i=2; i<=n; i++){
        cout << (N[i] == 1e9 ? 0 : N[i])  << ' ';
    }
}