当前没有测试数据。

题目描述

小X来到了ikun岛旅游，这里一共有 $n$ 个景点，一开始，小X在入口（ $1$ 号景点 ），最后小X最后要到达出口（ $n$ 号景点 ），每个景点 （ $2$ ~ $n$ ） 都有一个开放时间，一开始时间从 $0$ 开始， $t_{i,1}$ , $t_{i,2}$，代表 $t_{i,1}$ 开始 , $t_{i,2}$ 结束，请问小X到达出口的最早时间。

输入格式

$n$ ， $m$

$t_{2,1}$ ， $t_{2,2}$

$t_{3,1}$ ， $t_{3,2}$

$t_{4,1}$ ， $t_{4,2}$

......

$t_{n-1,1}$ ， $t_{n-1,2}$

表示第 $2$ 到 $n$ 景点的开放时间。

接下来 $m$ 行

每行 $3$ 个数 $u$ ， $v$ ， $w$ ，代表 $u$ 和 $v$ 景点中间有一条道路，小X可以花费 $w$ 时间从 $u$ 走到 $v$ 景点 或 从 $v$ 走到 $u$ 景点 。 注意: 小X非常勤劳，所以他不会到一个未开放景点等待，他到了当前景点时这个景点必须开放，不然他是不会走的!!!

输出格式

最短时间(数据保证能到达出口)。

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

8

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

6

提示

$1 \le u,v \le n \le 10^{5}$

$1 \le m \le 2 × 10^{5}$

$1 \le w \le 10^{9}$

$1 \le t_{i,1},t_{i,2} \le 10^{12}$