#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;

    for (int i = 0; i < N; i++) D[i] = INT64_MAX;
    D[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]});
    }

    unordered_set<int> done;
    

    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        done.insert(top.second);

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

    for (int i = 0; i < N; i++) {
        if (D[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;
}*/