#include <vector>
#include <algorithm>
#include <set>
#include <iostream>
using namespace std;
#define int long long

void mincammino(signed N, signed M, vector<signed> X, vector<signed> Y, vector<signed> P, vector<long long>& d) {
    int n=N,m=M;
    vector<int> x(m),y(m),p(m);
    for(int i=0;i<m;i++){
        x[i]=X[i];
        y[i]=Y[i];
        p[i]=P[i];
    }
    vector<vector<pair<int,int>>> g(n);
    for(int i=0;i<m;i++){
        g[x[i]].push_back({y[i],p[i]});
    }
    for(int i=0;i<n;i++) d[i]=1e18;
    set<pair<int,int>> st;
    st.insert({0,0});
    d[0]=0;
    while(!st.empty()){
        pair<int,int> v=*st.begin();
        st.erase(st.begin());
        for(auto i:g[v.second]){
            if(v.first+i.second<d[i.first]){
                st.erase(make_pair(d[i.first],i.first));
                d[i.first]=v.first+i.second;
                st.insert(make_pair(d[i.first],i.first));
            }
        }
    }
    for(int i=0;i<n;i++) if(d[i]==1e18) d[i]=-1;
}

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