题目描述

一场大型校园展览共有 $N$ 个展区，编号为 $1\sim N$。参观者从 $1$ 号展区出发，目标是到达 $N$ 号展区。

对于每个展区 $i\ (1\le i<N)$，都有两种离开方式：

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 个）