#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);
/*
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';
}
*/
void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<long long>& D) {
  priority_queue< pair < long long, int > > q;
  vector < vector < pair < int, int > > > adj (N);
  fill(D.begin(), D.end(), -1);
  for ( int i = 0; i < M; i++ ){
    adj[ X[i] ].push_back( {P[i], Y[i]});
  }
  int e1;
  long long p;
  for ( int i = 0; i < adj[0].size(); i++ ){
      q.push( { -adj[0][i].first, adj[0][i].second });
    }
  q.push( {0, 0 });
  while ( q.size() > 0 ){
    e1 = q.top().second;
    p = -q.top().first;
    q.pop();
    if ( D[e1] != -1 ) continue;
    D[e1] = p;
    for ( int i = 0; i < adj[e1].size(); i++ ){
      q.push( { -p-adj[e1][i].first, adj[e1][i].second });
    }
  }
}