#include <vector>
#include <algorithm>

#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++){
        adj[X[i]].push_back({Y[i], P[i]});
    }

    map<int, vector<int>> queue;
    queue.insert({0, {0}});

    vector<bool> visited(N, false);
    while (!queue.empty()){
        auto [d, xs] = *queue.begin();
        if (xs.size() == 0){
            queue.erase(d);
        }
        else {
            int x = xs.back();
            if (xs.size() == 1){
                queue.erase(d);
            }
            else {
                queue[d].pop_back();
            }

            if (visited[x]) continue;
            visited[x] = true;
            
            D[x] = d;
            for (auto [v, d] : adj[x]){
                queue[D[x]+d].push_back(v);
            }
        }
    }
    for (int i = 0; i < N; i++){
        if (!visited[i]){
            D[i] = -1;
        }
    }
}