#ABC340D. 最速通关

最速通关

题目描述

\hspace{15pt}一款游戏共有 nn 个关卡,编号为 1∼n1\sim n,最初只能游玩第 11 关。对于任意 i(1≦i<n)i\left(1\leqq i<n\right),当第 ii 关可以游玩时,可以任选以下一种操作:

∙ \hspace{23pt}\bullet\,花费 aia_i 秒通关第 ii 关,解锁第 i+1i+1 关;

∙ \hspace{23pt}\bullet\,花费 bib_i 秒通关第 ii 关,解锁第 xix_i 关。

\hspace{15pt}除通关耗时以外,其余时间忽略不计。求最早在多少秒后可以游玩第 nn 关,不需要再通关第 nn 关。

输入格式

\hspace{15pt}第一行输入一个整数 n(2≦n≦2×105)n\left(2\leqq n\leqq2\times10^5\right)。

\hspace{15pt}此后 n−1n-1 行,第 ii 行输入三个整数 $a_i,b_i,x_i\left(1\leqq a_i,b_i\leqq10^9;\ 1\leqq x_i\leqq n\right)$。跳转目标可以是当前关卡,也可以是编号更小的关卡。

输出格式

\hspace{15pt}输出一个整数,代表最早可以游玩第 nn 关的时间。答案可能超过 3232 位整数范围。

测试样例

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

样例 1 解释

\hspace{15pt}先花 100100 秒通过第 11 关,解锁第 22 关;再花 5050 秒通过第 22 关,解锁第 33 关;最后花 200200 秒通过第 33 关,解锁第 55 关。总时间为 350350 秒,且不存在更快的方案。

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