题目描述

农夫约翰有 $$ 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$ 单位时间。

数据范围与约定

农夫约翰有 $$ 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 ```input1 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 ``` ### 输出数据 1 ```output1 176 ``` ### 输入数据 2 ```input2 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 ``` ### 输出数据 2 ```output2 10637 ``` ### 输入数据 3 ```input3 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 ``` ### 输出数据 3 ```output3 10173 ```$$