题目背景

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$
$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春季トレーニング合宿 - 競技 4 - T3 日文题面。