#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) {
    priority_queue<pair<long long, int>> pq;

    vector<long long> dist(N, INT64_MAX);

    //for (int i = 0; i < N; i++) D[i] = INT64_MAX;
    dist[0] = 0;
    pq.push({0, 0});

    vector<vector<pair<int, int>>> mat(N); // first: chi, second: dist

    for (int i = 0; i < M; i++) {
        mat[X[i]].push_back({Y[i], P[i]});
    }

    vector<bool> done(N, false);

    long long sz = 1;

    while (sz > 0) {
        sz--;
        auto top = pq.top();
        pq.pop();
        done[top.second] = 1;

        for (auto vicino: mat[top.second]) {
            if(dist[vicino.first] > - top.first + vicino.second && (!done[vicino.first])) {
                dist[vicino.first] = - top.first + vicino.second;
                pq.push({-dist[vicino.first], vicino.first});
                sz++;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        D[i] = dist[i];
        if (dist[i] == INT64_MAX) D[i] = -1;
    }
}

/*int main() {
    int N = 4;
    int M = 5;
    vector<int> X = {0, 0, 1, 2, 2};
    vector<int> Y = {1, 2, 3, 1, 3};
    vector<int> P = {1, 2, 1, 3, 5};
    vector<long long> D(N, 0);

    mincammino(N, M, X, Y, P, D);
    for (auto e: D) cout << e << endl;
}*/