#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<array<int,2>>> G(N);
    for(int i=0; i<M; i++){
        G[X[i]].push_back({Y[i],P[i]});
    }
    priority_queue<pair<long long,int>> Q;
    Q.push({0,0});
    D.assign(N,-1);
    D[0]=0;
    while(!Q.empty()){
        pair<long long,int> q=Q.top();
        Q.pop();
        int a=q.second;
        int d=-q.first;
        if(d>D[a]) continue;
        for(int i=0; i<G[a].size(); i++){
            int b=G[a][i][0];
            int p=G[a][i][1];
            if(D[b]==-1||D[b]>D[a]+p){
                D[b]=D[a]+p;
                Q.push({-D[b],b});
            }
        }
    }
}
/*
int 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<<endl;
}*/