1
const int N = 1e5+5;
2

3
int n;
4
ll costs[N];
5
int din[N];
6
vector<int> adj[N];
7

8
struct e{
9
  int od;
10
  ll cost;
11

12
  bool operator<(const e& other) const{
13
    return cost>other.cost;
14
  }
15
};
16

17
ll toposort(){
18
  ll ans=0;
19
  priority_queue<e> q;
20
  for(int i=1;i<=n;i++){
21
    if(din[i]==0){
22
      q.push({i,costs[i]});
23
    }
24
  }
25
  while(!q.empty()){
26
    e x=q.top();
27
    q.pop();
28
    int node=x.od;
29
    ll c=x.cost;
30
    for(int y:adj[node]){
31
      if(--din[y]==0){
32
        q.push({y,c+costs[y]});
33
        ans=max(ans,c+costs[y]);
34
      }
35
    }
36
  }
37
  return ans;
38
}
39

40
void solve() {
41
    cin>>n;
42
  for(int i=1;i<=n;i++){
43
    int u,v;cin>>u;
44
    cin>>costs[u];
45
    cin>>v;
46
    while(v!=0){
47
      adj[v].push_back(u);
48
      din[u]++;
49
      cin>>v;
50
    }
51
  }
52
  ll ans=toposort();
53
  cout<<ans;
54
}