#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void mincammino (int n, int m, vector<int> a, vector<int> b, vector<int> c, vector<ll>& dist) {

  vector<vector<pair<int, ll>>> adj(n);
  for (int i = 0; i < m; ++i) adj[a[i]].push_back({b[i], c[i]});
  dist.assign(n, 1e13);
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  dist[0] = 0;
  pq.push({0, 0});

  while (!pq.empty()) {
    auto [w, u] = pq.top(); pq.pop();

    if (w < dist[u]) continue;
    for (auto [v, nw] : adj[u]) {
      if (dist[v] < dist[u] + nw) continue;

      dist[v] = dist[u] + nw;
      pq.push({dist[v], v});
    }
  }

  for (int i = 0; i < n; ++i) if (dist[i] == 1e13) dist[i] = -1;
}

/*
int main() {

  ll n, m; cin >> n >> m;

  vector<int> a(m), b(m), c(m);
  for (int i = 0; i < m; ++i) cin >> a[i] >> b[i] >> c[i];
  vector<ll> dist(n);

  mincammino(n, m, a, b, c, dist);
  for (int i : dist) cout << i << " ";
}
*/