#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> adi[300000]; //first arrivo second peso dell'arco

priority_queue<pair<long long,int>> qu;//first peso second nodo

void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<long long>& D){
    for(int i=0; i<M; i++){
        int da = X[i];
        int a = Y[i]; 
        int p = P[i];
        adi[da].push_back({a, p});
    }
    for(int i=0; i<D.size(); i++) D[i] = 1000000000*300000;
    D[0]=0;
    vector<bool> visitati(N, false);
    qu.push({0,0});
    while(!qu.empty()){
        auto u=qu.top(); qu.pop();
        long long p = u.first;
        int n = u.second;
        if(visitati[n]) continue;
        visitati[n] = true;
        //cout << n << endl;
        for(auto a : adi[n]){
            if(D[a.first] > p+a.second){
                D[a.first] = p+a.second;
                qu.push({D[a.first], a.first});
            }
        }
    }
    for(int i=0; i<D.size(); i++){
        if(D[i] == 1000000000*300000) D[i] = -1;
    }
    return;
    
}
/*
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';
}
*/