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

题目背景

星环城由一条主航道串联着若干座星港。每座星港都配备了两套调度方案：一种是沿主航道按顺序前往下一座星港；另一种是启用一次“曲率牵引”，将飞船直接牵引到某个指定星港。
由于不同星港的设备型号不同，每次调度耗时也不同。调度中心希望用最短时间把飞船从首港送到终港。

题目描述

共有 $N$ 座星港，编号为 $1\sim N$。飞船初始位于星港 $1$，目标到达星港 $N$。

对于每个 $i=1,2,\dots,N-1$，调度中心可以从星港 $i$ 选择以下两种方式之一出发：

1. 主航道推进：前往星港 $i+1$，耗时 $A_i$ 秒；
2. 曲率牵引：前往星港 $X_i$，耗时 $B_i$ 秒。

请计算：从星港 $1$ 到达星港 $N$ 的最短总耗时（秒数）。

输入格式

• 第一行一个整数 $N$。
• 接下来 $N-1$ 行，每行三个整数 $A_i$、$B_i$、$X_i$，表示从星港 $i$ 出发的两种调度方案。

输出格式

输出一个整数，表示从星港 $1$ 到达星港 $N$ 的最短总耗时。

输入输出样例

4
2 7 4
3 1 1
5 2 4

7

5
4 2 3
4 7 5
1 5 2
6 1 5

4

2
100 1 2

1

数据范围与约定

• $2 \le N \le 2\times 10^5$
• $1 \le A_i, B_i \le 10^9$
• $1 \le X_i \le N$
• 保证所有耗时为正整数

测试点设计（共 20 个）

测试点编号	规模
1–8	$N\le 8000$
9-20	无限制