问题描述

高桥在玩游戏。

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

对于每一关 $i(1\leq i\leq N-1)$，您可以执行以下两个操作之一：

• 花费 $A_i$ 秒来打破第 $i$ 关。这允许你接着玩第 $i+1$ 关。
• 花费 $B_i$ 秒来打破第 $i$ 关。这使您可以继续玩第 $X_i$ 关。

忽略游玩游戏关卡以外的时间（即两关之间的过场动画之类的），至少需要多少秒才能打到第 $N$ 关？

数据规模

$2\leq N\leq 2×10^5$

$1\leq A_i, B_i\leq 10^9$

$1\leq X_i\leq 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