#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]});
    }

    vector<bool> done(N, false);

    

    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        done[top.second] = 1;

        for (auto vicino: mat[top.second]) {
            if(D[vicino.first] > - top.first + vicino.second && (!done[vicino.first])) {
                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;
}