#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 2e5 + 5;
const int inf = 1e9 + 5 + 7 + 9;
vector<int> g[nmax];
int father[nmax], cost[nmax], height[nmax];
vector<int> naive[nmax];
int solved[nmax];
template<class CB> void fill(int a, int f, CB&& cb, vector<int> graph[nmax]) {
cb(a);
for(auto x : graph[a])
if(x != f)
fill(x, a, cb, graph);
return;
}
#define lsb(x) (x & -x)
struct AIB {
vector<int> v;
void init(int n_) { v.assign(n_ + 5, 0); }
int query(int a) {
int sum = 0;
while(a > 0) sum += v[a], a -= lsb(a);
return sum;
}
void update(int p, int x) {
while(p < sz(v)) v[p] += x, p += lsb(p);
}
};
namespace DS {
ll sol;
AIB occupied;
int pin[nmax], pout[nmax], inp;
int jump[nmax], p[nmax], d[nmax];
int budget[nmax];
void fill(int a, int f) {
//cerr << a << ' ' << f << '\n';
d[a] = d[f] + 1;
p[a] = jump[a] = f;
if(d[f] + d[jump[jump[f]]] == 2 * d[jump[f]]) jump[a] = jump[jump[f]];
pin[a] = inp++;
for(auto x : g[a])
if(x != f)
fill(x, a);
pout[a] = inp;
return;
}
void startProcedure(vector<int> nodes, vector<int> cycles) {
height[0] = -inf;
sol = 0;
inp = 1;
fill(0, 0);
map<int, ll> cyclefree;
for(auto x : cycles) solved[x] = 100, d[x] = -1;
copy(all(cycles), back_inserter(nodes));
map<pii, int> renrm;
for(auto x : nodes) renrm[make_pair(height[x], d[x])];
int cnt = 0;
for(auto &[a, b] : renrm) b = cnt++;
for(auto x : nodes) height[x] = renrm[make_pair(height[x], d[x])];
for(auto x : nodes) {
if(solved[x] == 100)
cyclefree[height[x]] += cost[x];
}
occupied.init(inp);
//cerr << "wow\n";
ll sum = 0, maxpossible = 0;
for(auto x : nodes) sum += cost[x];
sort(all(nodes), [&](int a, int b) { return height[a] > height[b]; });
for(auto x : nodes) budget[x] = 0;
auto anc = [&](int node) { return occupied.query(pin[node]); };
auto modnode = [&](int node, int p) { occupied.update(pin[node], p), occupied.update(pout[node], -p); };
for(auto x : nodes) {
int specialed = 0;
if(solved[x] == 100) {
specialed = cyclefree[height[x]];
}
else {
int mine = anc(x), upward = x, mybudget = cost[x];
while(mybudget > 0 && mine > 0) {
int tmp = upward;
while(upward != 0 && anc(upward) == mine) {
if(anc(jump[upward]) == mine) upward = jump[upward];
tmp = upward;
upward = p[upward];
}
upward = tmp;
if(upward != 0) {
int u = min(mybudget, budget[upward]);
mybudget -= u, budget[upward] -= u;
if(budget[upward] == 0) modnode(upward, -1), mine = anc(x);
}
}
sol += mybudget;
modnode(x, 1);
budget[x] = cost[x];
}
maxpossible = max(maxpossible, sol + specialed);
}
for(auto x : nodes) solved[x] = 1;
sol = sum - maxpossible;
return;
}
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> father[i] >> height[i] >> cost[i];
naive[i].emplace_back(father[i]);
naive[father[i]].emplace_back(i);
}
ll autoAdd = 0;
for(int i = 1; i <= n; i++) {
if(solved[i]) continue;
vector<int> nodes, cycles;
g[n + 1].clear(); g[0].clear();
g[0].emplace_back(n + 1); g[n + 1].emplace_back(0);
int x = i;
while(solved[x] == 0) {
solved[x] = -2;
x = father[x];
}
while(solved[x] == -2) {
solved[x] = -1;
x = father[x];
}
height[n + 1] = -inf;
cost[n + 1] = 0;
while(solved[x] == -1) {
cycles.emplace_back(x);
for(auto a : naive[x]) {
if(solved[a] != -1 && solved[a] != 1) {
fill(a, x, [&](int node) {
nodes.emplace_back(node);
if(solved[father[node]] == -1) g[node].emplace_back(n + 1), g[n + 1].emplace_back(node);
else g[node].emplace_back(father[node]), g[father[node]].emplace_back(node);
solved[node] = 1;
}, naive);
}
}
solved[x] = 1;
x = father[x];
}
DS::startProcedure(nodes, cycles);
autoAdd += DS::sol;
}
cout << autoAdd << '\n';
}
/**
Istenem! Nu poate fi real.
-- Surse verificate
*/
