#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> V[51000], C[52000];
ll N[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]){
                auto found = S.find({N[y],y}); 
                if(found != S.end()){ 
                    S.erase(found);
                    // cout << "erase " << N[y] << ' ' << y << '\n';
                }
                N[y] = N[d] + C[d][i];
                S.insert({N[y], y});
                // cout << "insert " << N[y] << ' ' << y << '\n';
            }
        }

        auto mini = S.begin();
        if(mini != S.end()){
            d = mini->second;
            S.erase(mini);
        } else {
            break;
        }
    }

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