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

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

  vector<vector<pair<int, ll>>> adj(n);
  for (int i = 0; i < m; ++i) {
    adj[a[i]].push_back({b[i], (ll)c[i]});
  }

  priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  d.assign(n, 1e18);
  d[0] = 0;
  pq.push({0LL, 0});

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

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

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

  for (int i = 0; i < n; ++i) {
    if (d[i] == 1e18) d[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 << " ";
}
*/