Problem Background

B Tarou is not cute.

Problem Description

B Tarou is a journalist primarily writing about OI. In a few days, the IOI is about to take place, and B Tarou decides to write an article about it.

The competition will have $n$ participants, each assigned a number from $1$ to $n$. Each participant has a Rating, which is a measure of their strength. The Rating is represented by an integer between $1$ and $10^9$.

B Tarou interviewed each participant and obtained the following information:

• The Rating of participant $i\ (1 \le i \le n)$ is greater than or equal to the Rating of participant $a_i\ (1 \le a_i \le n)$ (where $a_i$ can be equal to $i$).

After all the interviews, B Tarou received a table from the company managing the Rating system, listing the Rating of each participant. The table contains the following information:

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

When B Tarou tried to write an article based on this information, he found that the Rating table for each participant might contain errors.

Since the deadline is approaching, there is no time to correct the Rating table. Therefore, B Tarou decides to rewrite the Ratings in the table so that they do not contradict the information obtained from the interviews.

Rewriting the Rating of participant $i\ (1 \le i \le n)$ in the table costs B Tarou $c_i$ yen.

That is, B Tarou can change the Rating of participant $i$ in the list to any integer between $1$ and $10^9$ by paying $c_i$ yen. To meet the deadline, B Tarou wants to minimize the total cost of changing the Ratings in the list.

Write a program that, given the number of participants, the information obtained from the interviews, the Rating list, and the cost of changing each participant's Rating, calculates the minimum amount of yen required to make the list consistent with the interview information.

Input Format

The first line contains a single positive integer $n$.

The next $n$ lines each contain three positive integers, $a_i, h_i, c_i$.

Output Format

Output a single positive integer, representing the minimum amount of yen required to make the list consistent with the interview information.

Sample Input and Output

Sample Input #1

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

Sample Output #1

14

Sample Input #2

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

Sample Output #2

0

Sample Input #3

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

Sample Output #3

2711043927

Sample Input #4

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

Sample Output #4

4012295156

Notes/Hints

Sample #1 Explanation

The following table shows the changes:

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

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

Sample #2 Explanation

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

Sample #3 Explanation

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

Data Size and Constraints

This problem uses a Subtask scoring method.

Note: A slash indicates no special constraints.

For $100\%$ of the data:

• $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)$.

见题面 Input 部分

见题面 Output 部分