P7563 [JOISC 2021] Worst Reporter 4 (Worst Reporter 4) (Day4).

B Taro is not cute.

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.

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 a single positive integer: the minimum total cost in yen needed so that there is no contradiction with the interview information.

#### Explanation for Sample #1 As shown in the table below. | Contestant | Original Rating | Changed to | Cost (yen) | | :-: | :-: | :-: | :-: | | $1$ | $6$ | $1$ | $5$ | | $3$ | $8$ | $4$ | $4$ | | $5$ | $2$ | $10^9$ | $5$ | 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.** | Subtask | Score percentage | Special constraints | | :-: | :-: | :-: | | $1$ | $14\%$ | $n \le 5 \times 10^3$, $a_1 = 1$, $a_i \le i - 1$, and $2 \le i \le n$ | | $2$ | $65\%$ | $a_1 = 1$, $a_i \le i - 1$, and $2 \le i \le n$ | | $3$ | $21\%$ | / | **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 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Contest 4 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/2021-sp-d4-notice.pdf) [Task 3 Japanese statement](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/worst_reporter4.pdf). Translated by ChatGPT 5