#include <iostream>
#include <vector>
#include <queue>
#include <climits>
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>& dist){
    vector<vector<pair<ll,ll>>> adj(N);
    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>>> pq;
    vector<int> vis(N, false);
    dist.assign(N, LLONG_MAX);
    pq.push({0,0});
    dist[0]=0;
    
    while(!pq.empty()){
        ll nodo=pq.top().second;
        pq.pop();
        
        if(vis[nodo])continue;
        vis[nodo]=true;
        
        for(auto [x, w]: adj[nodo]){
            if(dist[x]>dist[nodo]+w){
                dist[x]=dist[nodo]+w;
                pq.push({dist[x], x});
            }
        }
        
    }
    
    for(int i=0; i<N; i++){
        if(dist[i]==LLONG_MAX){
            dist[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';
}

*/