本题没有可用的提交语言。

题目描述

农夫约翰有 $$ 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 1,000 $$）时间与奶牛交谈。

你将每晚固定住在同一个牧场（可自行选择），直到奶牛们恢复情绪。在每晚入睡前和早晨起床后，你至少需要与住处的奶牛交谈两次。

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

输入格式

• 第 $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 行：一个整数，表示拜访所有奶牛（包括在睡觉牧场进行的两次交谈）所需的总时间。

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