该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 $n$ 个关卡，编号分别为$1,2,3,...,n$，你正在参加一个闯关游戏,最开始，你在第 $1$ 关,在第 $i(1 \leq i \leq n -1)$ 关时，你可以进行如下操作：

①花费 $a_i$ 的时间从关卡 $i$ 来到关卡 $i + 1$.

②花费 $b_i$ 的时间从关卡 $i$ 来到关卡 $c_i$.

你想知道，到关卡 $n$ 需要花费的最少时间.

输入格式

第一行输入一个整数$n(2 \leq n \leq 200000)$

接下来输入 $n - 1$ 行，每行三个整数$a_i,b_i,c_i(1 \leq a_i,b_i \leq 10^9,1 \leq c_i \leq n)$

输入的数据含义与题目描述相同。

输出格式

一个整数，表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

350

样例 #2

样例输入 #2

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

样例输出 #2

5000000000