C. （汤姆汤姆巡航）

• 预估难度： CF 2300–2400
• 时间限制： 5 秒
• 空间限制： 256 MB
• 判题方式： 普通标准输出

题目描述

你计划从基地前往木卫三旅行。整段旅程都将使用同一艘宇宙飞船。

旅程需要消耗三部分燃料：

1. 从基地飞到木卫三上的某个地点；
2. 在木卫三表面经过若干地点；
3. 从最后一个地点返回基地。

木卫三上有一些可以访问的地点。地图被表示为一张无向图：

• 每个顶点表示一个地点；
• 顶点的权值表示在该地点与基地之间往返一次所需的燃料量；
• 每条边的权值表示在它连接的两个地点之间移动所需的燃料量。

为了让旅程合理，你不希望重复访问任何顶点，也不希望重复经过任何边。

但是，你必须至少经过一条边。

请计算完成这样一次旅程所需的最少燃料。

输入格式

第一行包含两个整数 $N,M$，分别表示顶点数和边数：

$$1\le N\le 10^4,$$ $$0\le M\le \min\left(\binom{N}{2},2\cdot10^4\right).$$

第二行包含 $N$ 个整数

$$v_0,v_1,\ldots,v_{N-1},$$

其中

$$1\le v_i\le10^6,$$

表示编号为 $0,1,\ldots,N-1$ 的顶点权值。

接下来 $M$ 行，每行包含三个整数 $f_i,t_i,w_i$：

$$0\le f_i,t_i<N,\qquad 1\le w_i\le10^6.$$

它们表示顶点 $f_i$ 与顶点 $t_i$ 之间有一条权值为 $w_i$ 的无向边。

输出格式

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

样例 1

输入

2 1
4 5
0 1 20

输出

29

样例 2

输入

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

输出

33