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

void mincammino(int n, int m, vector<int> x, vector<int> y, vector<int>p, vector<long long>& d){
    vector<vector<pair<int,int>>> adj(n);
    for(int i=0;i<m;i++){
        int a,b,c;
        a=x[i];
        b=y[i];
        c=p[i];
        adj[a].push_back({b,c});
    }
    d.assign(n,-1);
    priority_queue<pair<int,int>> pq;
    pq.push({0,0});
    while(!pq.empty()){
        int nodo=pq.top().second;
        int peso=-pq.top().first;
        pq.pop();
        if(d[nodo]!=-1){
            continue;
        }
        d[nodo]=peso;
        for(int i=0;i<adj[nodo].size();i++){
            int prossimo=adj[nodo][i].first;
            if(d[prossimo]==-1){
                pq.push({-(peso+adj[nodo][i].second),prossimo});
            }
        }
    }
}

/*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';
}*/