[JOISC 2021 Day4] 最悪の記者 4 (Worst Reporter 4)

B 太郎不可爱。

B 太郎是一名主要写关于 OI 的报道的记者。再过几天，就要举行 IOI 了，B 太郎决定写一篇关于 IOI 的文章。 比赛将有 $n$ 名选手参加，每位选手的编号从 $1$ 到 $n$。每位选手都有一个 Rating，这是衡量其实力的标准。Rating 用 $1$ 至 $10^9$ 之间的整数表示。 B 太郎采访了每位选手，并获得了以下信息： - 选手 $i\ (1\le i\le N)$ 的 Rating 大于等于选手 $a_i\ (1\le a_i \le n)$ 的 Rating。（$a_i$ 可以等于 $i$）。 在所有的采访结束后，B 太郎从管理 Rating 系统的公司收到了一张表格，上面有每个选手的 Rating。 表上写着以下信息： - 选手 $i\ (1 \le i \le n)$ 的 Rating 是 $h_i$。 当 B 太郎试图根据这些信息写一篇文章时，他发现每个选手的 Rating 表可能存在错误。 由于临近截止时间，没有时间去弄正确的 Rating 表。因此，B 太郎决定重写表中选手的 Rating，使其与采访中获得的信息不相矛盾。 B 太郎在表中改写选手 $i\ (1\le i \le n)$ 的 Rating 需要 $c_i$ 日元。 也就是说，B 太郎可以通过支付 $c_i$ 日元，将列表中选手 $i$ 的 Rating 更改为 $1$ 到 $10^9$ 之间的任意整数。为了在截止日期前完成任务，B 太郎想要最小化更改列表中 Rating 的总成本。 编写一个程序，给定选手的数量、采访获得的信息、Rating 列表、和更改每个选手 Rating 所用的花费。请你计算不与采访信息矛盾的情况下，最少需要花费多少日元。

第一行，一个正整数 $n$。 第 $2 \sim n + 1$ 行，每行三个正整数，$a_i,\ h_i,\ c_i$。

仅一行一个正整数，表示不与采访信息矛盾的情况下，最少需要花费的日元钱数。

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

#### 样例 #1 解释 如下表所示。 | 选手 | 原 Rating | 更改为 | 花费日元 | | :-: | :-: | :-: | :-: | | $1$ | $6$ | $1$ | $5$ | | $3$ | $8$ | $4$ | $4$ | | $5$ | $2$ | $10^9$ | $5$ | 花费了 $5+4+5=14$ 日元。 本样例满足 Subtask $1, 2, 3$。 #### 样例 #2 解释 信息一致，输出 $\tt 0$。 #### 样例 #3 解释 本样例满足 Subtask $1, 2, 3$。 #### 数据规模与约定 **本题采用 Subtask 计分法。** | Subtask | 分值占比百分率 | 特殊限制 | | :-: | :-: | :-: | | $1$ | $14\%$ | $n \le 5 \times 10^3$，$a_i = 1$，$a_i \le i - 1$，且 $2 \le i \le n$ | | $2$ | $65\%$ | $a_1 = 1$，$a_i \le i - 1$，且 $2 \le i \le n$ | | $3$ | $21\%$ | / | **注：斜线表示无特殊限制。** 对于 $100\%$ 的数据： - $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)$； #### 说明 本题译自 [第２０回日本情報オリンピック 2020/2021春季トレーニング合宿 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [競技 4 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/2021-sp-d4-notice.pdf) [T3 日文题面](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/worst_reporter4.pdf)。