// @check-accepted: tree bfs bellman-ford completa
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

constexpr long long INF = 1e18;

void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<long long>& D) {
    vector<vector<pair<int, long long>>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[X[i]].emplace_back(Y[i], P[i]);
    }
    
    fill(D.begin(), D.end(), INF);
    vector<bool> visited(N);
    priority_queue<
        pair<long long, int>,
        vector<pair<long long, int>>,
        greater<pair<long long, int>>
    > q;

    q.emplace(D[0] = 0, 0);
    while (!q.empty()) {
        auto [d, n] = q.top(); q.pop();
        if (visited[n]) continue;
        visited[n] = true;

        for (auto [x, w]: adj[n]) {
            if (d + w < D[x]) {
                q.emplace(D[x] = d + w, x);
            }
        }
    }

    transform(D.begin(), D.end(), D.begin(), [](long long x) { return x != INF ? x : -1; });
}