题目描述

给出 $N$ 个点 $M$ 条双向边的无向图。

每条边 $x_i \ y_i \ L_i$，表示这条边连接 点 $x_i$ 和 点 $y_i$，经过该边需要耗时 $L_i$。

每个点有个权值 $C_i$，表示经过该点需要耗时 $C_i$。

现在要删一些边，只保留 $N-1$ 条边，且所有点连通（一棵树）。

求从某个点出发，访问所有点至少一次，最后回到出发点的总耗时，要是总耗时最小（若以出发点为树根，树中所有非叶子节点访问两次，叶子节点访问一次）。

输入格式

第一行两个整数 $N \ M \ ( 5 \leq N \leq 10^4 , N-1 \leq M \leq 10^5)$

下来 $N$ 个整数 $C_i \ ( 1 \leq C_i \leq 1000 )$ 。

下来 $N$ 行，每行三个整数 $x_i \ y_i \ L_i \ (0 \leq L_i \leq 1000 )$。

输出格式

一行一个整数，表示所需的最小总时间。

输入

5 7 
10 
10 
20 
6 
30 
1 2 5 
2 3 5 
2 4 12 
3 4 17 
2 5 15 
3 5 6 
4 5 12

输出

176

说明/提示

   +-(15)-+
  /        \
 /          \
1-(5)-2-(5)-3-(6)--5
   \   /(17)  /
(12)\ /      /(12)
     4------+

保留这些路径：
1-(5)-2-(5)-3      5
       \          /
    (12)\        /(12)
        *4------+

选择牧场 $4$ 作为住处，按照 $4→5→4→2→3→2→1→2→4$ 的顺序拜访所有牧场，最终返回睡觉，总耗时为 $176$ 单位时间。