题目描述

强哥参加了一个刺激的密室逃脱游戏，这个游戏有 $N$ 个密室，编号为 $1$ 到 $N$ 。游戏开始时，强哥只能进入第一个密室。

在每个密室 $i（1≤i≤N-1）$，强哥有两种逃脱选择：

1. 花费 $A\_i$ 分钟找到常规出口，可以进入下一个密室 $i+1$
2. 花费 $B\_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

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