#include <vector>
#include <algorithm>
using namespace std;
vector<vector<pair<int,int>>>legami;
vector<long long>valori;
void assegna_r(int nodo){
//vector<pair<int,int>>targets=legami[nodo];
for(int i=0;i<legami[nodo].size();i++){
    int omega=valori[nodo]+legami[nodo][i].second;
    if(omega<valori[legami[nodo][i].first]){
        valori[legami[nodo][i].first]=omega;
        assegna_r(legami[nodo][i].first);
    }
}
}
void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<long long>& D) {
    legami=vector<vector<pair<int,int>>>(N);
    for(int i=0;i<M;i++){
        legami[X[i]].push_back({Y[i],P[i]});
    }
    valori=vector<long long>(N,1000000000000000);
    valori[0]=0;
    assegna_r(0);
    D=valori;
    return;
}