漂流

题目描述

奶龙漂流到了一片群岛.

可以认为这片海域有 $n$ 个岛屿, $m$ 条航路. 奶龙登陆岛屿 $i$ 需要消耗 $a_i$ 的时间, 沿着航路 $i$ 从一端划船到另一端需要消耗 $w_i$ 的时间。

因为奶龙可以化作龙舟, 可以快速通过某段航路, 把时间消耗变成 $0$. 但是奶龙的能量有限, 所以从岛 $i$ 到岛 $j$ 的航线上, 只能选择其中一条航路变成龙舟, 剩下的航路还要划船. 奶龙很聪明, 会规划总耗时最短的航线, 记 $\text{dis}(i,j)$ 表示从 $i$ 到 $j$ 的所有航线中, 允许选择至多一条航路, 使其耗时变成 $0$ 后的总耗时的最小值.

由于从 $i$ 到 $j$ 后, 奶龙还需要花费 $a_j$ 时间登陆, 所以奶龙的总耗时为: $c(i,j) = \text{dis}(i,j) + a_j$.

假如奶龙位于岛 $s$, 它已经把岛上的食物吃光了, 可是奶龙很能吃, 所以他的肚子又饿了. 他会登陆最快可以登陆的岛吃东西. 也就是花费 ${\min \{c(s,t)\}}$ 的时间. 你可以选择任意岛（包括 $s$ 本身）作为点 $t$.

暴暴龙可以将奶龙任意投放到某个岛上, 他想让奶龙尽可能饿更久, 你要帮奶龙计算, 最坏情况下他要饿多久.

输入格式

第一行包含有 $2$ 个正整数：$n,m$ , 表示岛屿数和航路数。

接下来 $m$ 行，每行包含 $3$ 个整数 $u_i$ , $v_i$ 和 $w_i$ ，表示一条航路。

最后 $1$ 行包含 $n$ 个正整数, 表示登陆每个岛屿的时间 $a_i$.

题目保证群岛抽象成的图是联通的且没有重边和自环。

输出格式

输出 $1$ 个正整数，表示奶龙饿肚子最久是多长时间.

输入输出样例

输入 #1

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

输出 #1

9

输入 #2

6 8
3 4 12
6 5 18
3 6 20
4 1 11
3 1 10
4 2 19
2 6 10
6 1 15
47 30 57 6 71 93

输出 #2

32

说明 / 提示

对于第一组样例, 奶龙被投放到每个岛上, 最短饿肚子的时间分别为 $8,9,8,8$, 暴暴龙会将他投放到第 $2$ 座岛屿, 所以答案为 $9$.

对于第二组样例, 奶龙被投放到每个岛上, 最短饿肚子的时间分别为 $6,6,6,6,32,16$, 暴暴龙会将他投放到第 $5$ 座岛屿, 所以答案为 $32$.

数据范围与约定

对于 $30\%$ 的数据，满足 $n \leq 50$ 且 $m \leq 300$.

对于另外 $20\%$ 的数据，满足 $m = n - 1$.

对于所有的数据，保证 $2\leq n \leq 10^{5}, 1\leq m \leq 5 \times 10^5, 1 \leq u,v \leq n, 1 \leq w_i \leq 10^6,1 \leq a_i \leq 10^{11}$。