Description

B Taro is a reporter who mainly writes reports about OI. In a few days, IOI will be held, and B Taro decided to write an article about IOI.

There will be $n$ contestants in the contest, numbered from $1$ to $n$. Each contestant has a Rating, which is a measure of their skill. A Rating is an integer between $1$ and $10^9$.

B Taro interviewed each contestant and obtained the following information:

• The Rating of contestant $i\ (1\le i\le N)$ is greater than or equal to the Rating of contestant $a_i\ (1\le a_i \le n)$ ($a_i$ may be equal to $i$).

After all interviews, B Taro received a table from the company that manages the Rating system, which contains each contestant’s Rating. The table states:

• The Rating of contestant $i\ (1 \le i \le n)$ is $h_i$.

When B Taro tried to write an article based on this information, he found that the table of each contestant’s Rating might contain mistakes.

Because the deadline is near, there is no time to obtain the correct Rating table. Therefore, B Taro decided to rewrite the contestants’ Ratings in the table so that they do not contradict the information obtained in the interviews.

To rewrite the Rating of contestant $i\ (1\le i \le n)$ in the table costs $c_i$ yen.

That is, by paying $c_i$ yen, B Taro can change contestant $i$’s Rating in the table to any integer between $1$ and $10^9$. To finish before the deadline, B Taro wants to minimize the total cost of changing Ratings in the table.

Write a program that, given the number of contestants, the interview information, the Rating table, and the cost of changing each contestant’s Rating, computes the minimum total cost (in yen) needed so that the table does not contradict the interview information.

Input Format

The first line contains a positive integer $n$.

Lines $2$ to $n + 1$ each contain three positive integers $a_i, h_i, c_i$.

Output Format

Output a single positive integer: the minimum total cost in yen needed so that there is no contradiction with the interview information.

6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6

14

5
1 1 1
2 2 1
4 3 1
3 3 1
4 3 1

0

20
1 7 381792936
1 89 964898447
1 27 797240712
3 4 299745243
2 18 113181438
2 20 952129455
4 34 124298446
4 89 33466733
7 40 109601410
5 81 902931267
2 4 669879699
8 23 785166502
8 1 601717183
8 26 747624379
1 17 504589209
9 24 909134233
16 56 236448090
8 94 605526613
5 90 481898834
9 34 183442771

2711043927

20
15 62 418848971
13 5 277275513
14 60 80376452
12 14 256845164
12 42 481331310
6 86 290168639
3 98 947342135
3 19 896070909
16 39 48034188
8 29 925729089
18 97 420006994
13 51 454182928
19 61 822405612
13 37 148425187
15 77 474094143
14 27 272926693
18 43 566552069
9 93 790433300
10 73 61654171
14 28 334498030

4012295156

Hint

Explanation for Sample #1

As shown in the table below.

The total cost is $5+4+5=14$ yen.

This sample satisfies Subtasks $1, 2, 3$.

Explanation for Sample #2

The information is consistent, so output $\tt 0$.

Explanation for Sample #3

This sample satisfies Subtasks $1, 2, 3$.

Constraints and Notes

This problem uses Subtask scoring.

Note: A slash means there are no special constraints.

For $100\%$ of the testdata:

• $2 \le n \le 2 \times 10^5$.
• $1 \le a_i \le n\ (1\le i\le n)$.
• $1\le h_i,\ c_i \le 10^9\ (1\le i\le n)$.

Statement Source

This problem is translated from The 20th Japanese Olympiad in Informatics 2020/2021 Spring Training Camp - Contest 4 - Task 3 Japanese statement.

Translated by ChatGPT 5