#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>>> matr(N);
  for(int i = 0; i < M; i++) {
    matr[X[i]].push_back({Y[i], P[i]});
  }
  priority_queue<pair<int, int>> pq;
  vector<int> vis(N, 0);
  vector<long long> dist(N, 1e15);
  dist[0] = 0;
  pq.push({0, 0});
  while(!pq.empty()) {
    int amadu = pq.top().second;
    pq.pop();
    if(vis[amadu] == 0) {
      vis[amadu] = 1;
      for(int i = 0; i < matr[amadu].size(); i++) {
        int Coach = matr[amadu][i].first;
        int Claudio = matr[amadu][i].second;
        //cout << amadu << " "<< Coach << " " << Claudio << " " << dist[amadu] << endl;
        if(dist[Coach] > dist[amadu] + Claudio) {
          dist[Coach] = dist[amadu] + Claudio;
          pq.push({-dist[Coach], Coach});
        }
      }
    }
  }
  for(int i = 0; i < N; i++) {
    if(dist[i] == 1e15) {
      D[i] = -1;
    } else {
      D[i] = dist[i];
    }
  }
}