Code : Super Takahashi Bros.

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

const long long inf = 1e15;

class Graph {
  public:
    int n;
    vector<vector<pair<int, int>>> adj;
    Graph(int n) {
        this->n = n;
        adj.resize(n);
    }

    vector<long long> dijkstra(int src) {
        vector<long long> d(n, inf);
        set<pair<long long, int>> heap;

        d[src] = 0;
        for (int i = 0; i < n; i++) {
            heap.insert({d[src], src});
        }

        for (int i = 0; i < n; i++) {
            int u = heap.begin()->second;
            heap.erase(heap.begin());

            for (auto [c, w] : adj[u]) {
                auto nxt = d[u] + w;
                if (d[c] > nxt) {
                    heap.erase({d[c], c});
                    d[c] = nxt;
                    heap.insert({d[c], c});
                }
            }
        }

        return d;
    }
};

void solve() {
    int n;
    cin >> n;

    Graph g(n);
    auto &adj = g.adj;
    for (int i = 0; i < (n - 1); i++) {
        int a, b, x;
        cin >> a >> b >> x;
        x--;
        adj[i].push_back({i + 1, a});
        adj[i].push_back({x, b});
    }

    cout << g.dijkstra(0)[n - 1] << endl;
}

int main() {
    solve();
    return 0;
}