超级高桥兄弟

题目描述

高桥君正在玩一个游戏。

游戏由编号为 $1,2,\ldots,N$ 的 $N$ 个关卡组成。最初只能游玩关卡 $1$。

对于每个可以游玩的关卡 $i$（$1 \le i \le N-1$），你可以在关卡 $i$ 执行以下两种操作之一：

• 花费 $A_i$ 秒通关关卡 $i$，从而可以游玩关卡 $i+1$。
• 花费 $B_i$ 秒通关关卡 $i$，从而可以游玩关卡 $X_i$。

忽略通关关卡以外的耗时，最少需要多少秒才能游玩到关卡 $N$？

输入格式

输入按以下格式从标准输入给出：

$N$
$A_1$ $B_1$ $X_1$
$A_2$ $B_2$ $X_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$ $X_{N-1}$

输出格式

输出答案。

样例

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

350

按照以下方式操作，$350$ 秒后即可游玩关卡 $5$。

花费 $100$ 秒通关关卡 $1$，从而可以游玩关卡 $2$。

花费 $50$ 秒通关关卡 $2$，从而可以游玩关卡 $3$。

花费 $200$ 秒通关关卡 $3$，从而可以游玩关卡 $5$。

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 \le 2 \times 10^5$
• $1 \le A_i, B_i \le 10^9$
• $1 \le X_i \le N$
• 所有输入值均为整数