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

vector<int> getMinimumLength(int roads_nodes, vector<int> roads_from, vector<int> roads_to, vector<int> roads_weight) {
    const int n = roads_nodes;
    const int m = (int)roads_from.size();

    vector<vector<pair<int,int>>> adj(n + 1), rev(n + 1);
    for (int i = 0; i < m; ++i) {
        adj[roads_from[i]].push_back({roads_to[i], roads_weight[i]});
        rev[roads_to[i]].push_back({roads_from[i], roads_weight[i]});
    }

    const long long INF = LLONG_MAX;
    vector<long long> dist(n + 1);
    vector<int> result(n, 0);
    using P = pair<long long, int>;

    for (int x = 1; x <= n; ++x) {
        fill(dist.begin(), dist.end(), INF);
        dist[x] = 0;

        priority_queue<P, vector<P>, greater<P>> pq;
        pq.push({0, x});

        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            for (auto [v, w] : adj[u]) {
                long long nd = d + w;
                if (nd < dist[v]) {
                    dist[v] = nd;
                    pq.push({nd, v});
                }
            }
        }

        long long best = INF;
        for (auto [u, w] : rev[x]) {
            if (dist[u] != INF) best = min(best, dist[u] + (long long)w);
        }
        result[x - 1] = (best == INF) ? 0 : (int)best;
    }
    return result;
}

// ---------- Test harness ----------
static void runTest(const string& name,
                    int n,
                    vector<int> from, vector<int> to, vector<int> w,
                    vector<int> expected) {
    vector<int> got = getMinimumLength(n, from, to, w);

    cout << name << "\n";
    cout << "  Expected: [";
    for (size_t i = 0; i < expected.size(); ++i)
        cout << expected[i] << (i + 1 < expected.size() ? ", " : "");
    cout << "]\n";

    cout << "  Got:      [";
    for (size_t i = 0; i < got.size(); ++i)
        cout << got[i] << (i + 1 < got.size() ? ", " : "");
    cout << "]\n";

    cout << "  " << (got == expected ? "PASS" : "FAIL") << "\n\n";
}

int main() {
    // Problem-statement example: 4 nodes, edges 1->2:14, 2->3:23, 3->1:23, 4->3:30
    runTest("Example (problem statement)",
            4,
            {1, 2, 3, 4},
            {2, 3, 1, 3},
            {14, 23, 23, 30},
            {60, 60, 60, 0});

    // Sample Case 0: triangle 1->2->3->1, all weights 10
    runTest("Sample Case 0",
            3,
            {1, 2, 3},
            {2, 3, 1},
            {10, 10, 10},
            {30, 30, 30});

    // Sample Case 1: 4 nodes, 5 edges
    // 1->3:20, 3->2:25, 2->1:15, 4->2:10, 1->4:5
    runTest("Sample Case 1",
            4,
            {1, 3, 2, 4, 1},
            {3, 2, 1, 2, 4},
            {20, 25, 15, 10, 5},
            {30, 30, 60, 30});

    return 0;
}