题目描述

小泽正在挑战一款由 $N$ 个关卡组成的游戏，关卡编号为 $1,2,\ldots,N$。游戏开始时，他只能游玩关卡 $1$。

对于每个关卡 $i$（$1\le i\le N-1$），只要这个关卡已经可以游玩，小泽就可以选择下面两种方式中的一种完成它：

• 花费 $A_i$ 秒完成关卡 $i$，随后关卡 $i+1$ 变为可以游玩；
• 花费 $B_i$ 秒完成关卡 $i$，随后关卡 $X_i$ 变为可以游玩。

除了完成关卡所需的时间以外，其他操作耗时都可以忽略。已经可以游玩的关卡之后仍然可以再次进入，因此小泽可以根据需要选择不同的关卡继续行动。

请计算从游戏开始到关卡 $N$ 第一次变为可以游玩，最少需要经过多少秒。

输入格式

第一行输入一个整数 $N$。

接下来 $N-1$ 行，第 $i$ 行输入三个整数 $A_i,B_i,X_i$。

输出格式

输出一个整数，表示使关卡 $N$ 变为可以游玩所需的最短时间。

5
100 200 3
50 10 1
100 200 5
150 1 2

350

10
1000 10 9
1000 10 10
1000 10 2
1000 10 3
1000 10 4
1000 10 5
1000 10 6
1000 10 7
1000 10 8

90

6
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1

5000000000

数据范围与约定

$2\le N\le2\times10^5$，$1\le A_i,B_i\le10^9$，$1\le X_i\le N$。输入中的所有数均为整数。