#include <bits/stdc++.h>
using namespace std;
vector<int> V[51000], C[52000];
int N[51000], Z[5100];
int l, n, gasite;
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=2; i<=n; i++){
        N[i] = 1e9;
        Z[i] = 0;
    }
    N[1] = 0;
    Z[1] = 0;
    d = 1;
    int n1 = n;
    while(n1--){
        for(int i=0; i<V[d].size(); i++){
            if(N[d] + C[d][i] < N[V[d][i]]){
                N[V[d][i]] = N[d] + C[d][i];
            }
        }

        long long mn =1e9;
        for(int i=1; i<=n; i++){
            if(N[i] < mn && !Z[i]){
                mn = N[i];
                d = i;
            }
        }
        Z[d] = 1;
    }

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