#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1000000000000000LL

vector<ll> Dijkstra(int source, int n, vector<vector<pair<ll,int>>>graph){
    vector<bool>vis(n,false);
    vector<ll>dist(n,INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>>pq;

    dist[source] = 0;
    pq.push({0,source});
    while(!pq.empty()){
        auto [d,node] = pq.top();
        pq.pop();
        if (!vis[node]){
            vis[node]=true;
            for (auto [w,adj] : graph[node]){
                ll new_dist = d + w;
                if (new_dist < dist[adj]){
                    dist[adj] = new_dist;
                    pq.push({new_dist, adj});
                }
            }
        }
    }

    for (auto &e : dist) if (e>=INF) e = -1;
    return dist;
}

void mincammino(int n, int m, vector<int>x, vector<int>y, vector<int>p, vector<ll>&d){
    vector<vector<pair<ll,int>>>graph(n);
    for (int i=0; i<m; i++){
        graph[x[i]].push_back({p[i],y[i]});
    }
    d = Dijkstra(0, n, graph);
    return;
}


#ifndef EVAL
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';
}
#endif