题目描述
LHX 正在玩一个游戏。
游戏由编号为 $1,2,\ldots,N$ 的 $N$ 个阶段组成。最初，只有阶段 $1$ 可以下。
对于每个可以选择的阶段 $i$ ( $1\leq i \leq 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}$
- $2 \leq N \leq 2\times 10^5$
- $1 \leq A_i, B_i \leq 10^9$
- $1 \leq X_i \leq N$
- 所有输入值均为整数。
5
100 200 3
50 10 1
100 200 5
150 1 2
提示
样例 1
按照以下步骤操作，您将可以在 $350$ 秒内进入 $5$ 阶段。
- 花费 $100$ 秒清除 $1$ 阶段，从而可以游玩 $2$ 阶段。
- 花费 $50$ 秒通关 $2$ 关卡，从而可以游玩 $3$ 关卡。
- 花费 $200$ 秒钟通关 $3$ 关卡，从而可以游玩 $5$ 关卡。