你打算从基地出发前往木卫三（Ganymede）进行一次旅行。你有一艘宇宙飞船，将用于整个行程。前往木卫三需要消耗一定的燃料，在木卫三上移动需要消耗燃料，返回基地也需要消耗燃料。

木卫三上有若干个你可以访问的地点。木卫三的地图由一个图给出，其中每个顶点的权重等于从该点往返基地所需的燃料量。每条边的权重等于在由该边连接的两个顶点之间往返所需的燃料量（双向均可）。

为了使你的行程合理，你不希望访问任何边或任何顶点超过一次。但是，你必须至少经过一条边。

完成这样一次旅行所需的最少燃料是多少？

输入格式

输入的第一行包含两个整数 $N$ 和 $M$，分别表示顶点数和边数（$1 \le N \le 10^4$，$0 \le M \le \min \binom{N}{2}, 2 \cdot 10^4$）。下一行包含 $N$ 个整数 $v_0, v_1, \dots, v_{N-1}$（$1 \le v_i \le 10^6$），分别表示顶点 $0, 1, \dots, N-1$ 的权重。接下来的 $M$ 行中，每行包含三个整数 $f_i, t_i$ 和 $w_i$（$0 \le f_i, t_i < N$，$1 \le w_i \le 10^6$），分别表示该边连接的两个顶点以及边的权重。

输出格式

输出你完成旅行所需的最少燃料。

样例

样例输入 1

2 1
4 5
0 1 20

样例输出 1

29

样例输入 2

3 3
10 40 20
0 1 1
0 2 4
2 1 2

样例输出 2

33