#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
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>>> adj(N);
  for(int i=0;i<N;i++){
    adj[X[i]].push_back({P[i],Y[i]});
  }
  for(int i=0;i<N;i++) D[i]=1e18;
  vector<bool> vis(N,0);
  priority_queue<pair<long long,int>> q;
  D[0]=0;
  q.push({0,0});
  while(!q.empty()){
    int a=q.top().second;
    long long W=q.top().second;
    q.pop();
    if(vis[a]==1) continue;
    vis[a]=1;
    for(auto [w,b]: adj[a]){
      if(D[a]+w<D[b]){
        D[b]=D[a]+w;
        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 << '\n';
}*/