题目描述

农场主小明拥有 $N$（$5 \leq N \leq 10000$）个牧场，编号 $1$ 到 $N$，每个牧场里住着一头奶牛。这些牧场之间由 $P$（$N-1 \leq P \leq 100000$）条双向道路连通。第 $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 1000$）单位时间。任意两个牧场之间至多只有一条直接相连的道路。

小明想要在保持所有牧场连通的前提下，删除尽可能多的道路。然而道路拆除后奶牛们会很伤心，因此他计划拆完道路后逐个牧场去安抚奶牛。小明可以从任意一个牧场出发开始安抚工作，走遍所有奶牛后再回到出发地。每次经过牧场 $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$。

输出格式

一行一个整数，表示安抚所有奶牛（包括在起始牧场的两次交谈）所需的最小总时间。

样例

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

提示

保留边 $(1,2)$、$(2,3)$、$(2,4)$、$(4,5)$，以牧场 $4$ 为起始点，按 $4 \to 5 \to 4 \to 2 \to 3 \to 2 \to 1 \to 2 \to 4$ 的路线行走，总耗时 $176$ 单位时间。