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