题目描述

农夫约翰有 $N$ 个牧场（编号为 $1$ 到 $N$，$5 \leq N \leq 10,000$），每个牧场住着一头牛。这些牧场通过 $P$ 条双向路径（$N-1 \leq P \leq 100,000$）连接。每条路径 $j$ 连接牧场 $S_j$ 和 $E_j$（$1 \leq S_j \leq N$；$1 \leq E_j \leq N$；$S_j \neq E_j$），穿越该路径需要耗费 $L_j$（$0 \leq L_j \leq 1,000$）单位时间。任意两座牧场之间最多只有一条直接相连的路径。

约翰打算在保持各牧场连通的情况下去掉尽量多的道路。约翰知道，在道路被强拆后，奶牛会非常伤心，所以他计划拆除道路之后就去安抚她们。约翰可以选择从任意一个牧场出发开始他的安抚工作。当他走访完所有的奶牛之后，还要回到他的出发地。每次路过牧场 $i$ 的时候，他必须花 $C_i( 1 \leq C_i \leq 1000 )$ 的时间和奶牛交谈，即使之前已经谈过了，也要留下来再谈一次。注意约翰在出发和回去的时候，都要和出发地的奶牛谈一次话。

假设农夫约翰采纳了你关于保留路径的建议，并且你选择了最优的住宿牧场，请计算满足每天至少拜访每头牛一次的前提下，所需的最小总时间。

输入格式

• 第 $1$ 行：两个用空格分隔的整数：$N$ 和 $P$

• 第 $2$ 行到第 $N+1$ 行：第 $i+1$ 行包含一个整数：$C_i$ 。

• 第 $N+2$ 行到第 $N+P+1$ 行：第 $N+j+1$ 行包含三个用空格分隔的整数：$S_j$、$E_j$ 和 $L_j$。

输出格式

• 第 1 行：一个整数，表示拜访所有奶牛（包括在睡觉牧场进行的两次交谈）所需的最小总时间。

说明/提示

   +-(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$ 单位时间。

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

8 24
431
736
208
990
890
621
143
931
1 2 407
2 3 256
2 4 568
2 5 438
5 6 295
3 7 358
3 8 575
2 8 303
3 1 304
4 3 899
7 4 759
2 6 594
6 7 510
7 1 456
1 5 379
6 3 695
8 7 25
4 6 788
7 2 7
4 8 347
8 6 649
8 1 748
5 3 333
5 7 874

10637

11 33
129
322
222
868
842
505
555
410
177
236
398
1 2 511
2 3 412
2 4 163
3 5 14
4 6 992
6 7 4
6 8 848
7 9 480
9 10 971
3 11 775
2 8 638
5 2 922
6 3 461
9 2 65
9 6 439
5 1 716
11 4 95
9 5 215
8 10 710
10 6 68
1 6 669
2 10 240
7 4 184
11 5 385
9 1 246
2 7 216
7 3 162
1 3 253
3 8 467
1 11 126
3 4 125
1 10 410
4 1 960

10173

数据范围与约定

农夫约翰有 $N$ 个牧场（编号为 $1$ 到 $N$，$5 \leq N \leq 10,000$），每个牧场住着一头牛。

这些牧场通过 $P$ 条双向路径（$N-1 \leq P \leq 100,000$）连接。

每条路径 $j$ 连接牧场 $S_j$ 和 $E_j$（$1 \leq S_j \leq N$；

$1 \leq E_j \leq N$；

$S_j \neq E_j$），穿越该路径需要耗费 $L_j$（$0 \leq L_j \leq 1,000$）单位时间。

每次路过牧场 $i$ 的时候，他必须花 $C_i( 1 \leq C_i \leq 1000 )$ 的时间和奶牛交谈，即使之前已经谈过了，也要留下来再谈一次。