#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll=long long;
void mincammino(int n, int m, vector<int> X, vector<int> y, vector<int> p, vector<long long>& d) {
    vector<vector<pair<ll,ll>>> adj(n);
    fill(d.begin(),d.end(),10000000000000000);
    for (int i=0;i<m;i++) adj[X[i]].push_back({y[i],p[i]});
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll>>> q;
    q.push({0,0});
    while (!q.empty()){
        pair<ll,ll> p=q.top();q.pop();
        ll v=p.second,l=p.first;
        if (d[v]<=l) continue;
        d[v]=l;
        for (auto [x,val]:adj[v]){
            if (d[x]<=l+val) continue;
            q.push({l+val,x});
        }
    }
    for (int i=0;i<n;i++) if (d[i]==10000000000000000) d[i]=-1;
}


int main() {
    int N, M;
    cin >> N >> M;

    vector<int> X(M), Y(M), P(M);
    vector<long long> D(N);

    for (int i = 0; i < M; i++) {
        cin >> X[i] >> Y[i] >> P[i];
    }

    mincammino(N, M, X, Y, P, D);

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