Farmer John は怠け者で、全 $N$ 牧草地（$5\le N\le10{,}000$、番号 $1\ldots N$）に行ける道を維持したくありません。各地に牛 1 頭がいます。連結を保って $P$ 本（$N-1\le P\le100{,}000$）からできるだけ削除し、残す $N-1$ 本を決めます。

双方向の道 $j$ は $S_j,E_j$（$1\le S_j\le N;1\le E_j\le N;S_j\ne E_j$）を結び、時間 $L_j$（$0\le L_j\le1{,}000$）が必要です。同じ 2 地を直接結ぶ道は最大 1 本です。

交通網が縮小して牛は悲しんでいます。毎日各牛を最低 1 回訪れて元気づけます。牧草地 $i$ に来るたび、通過だけでも $C_i$ 時間（$1\le C_i\le1{,}000$）話す必要があります。

牛が元気になるまで、選んだ同じ牧草地で毎晩寝ます。そこの牛とは少なくとも朝の起床時と夕方戻って寝る時に話します。

提案した道を FJ が残し、最適な寝場所を選んだとき、毎日各牛を最低 1 回訪れる最小総時間を求めます。

最初の $10$ 回の提出には実際のテストの一部での実行結果が与えられます。

入力

• 第 $1$ 行：空白区切りの整数 $N,P$。

• 第 $2\ldots N+1$ 行：第 $i+1$ 行に整数 $C_i$。

• 第 $N+2\ldots N+P+1$ 行：第 $N+j+1$ 行に空白区切りの整数 $S_j,E_j,L_j$。

出力

• 第 $1$ 行：全牛を訪れる総時間の整数。寝場所の牛を 2 回訪れる時間も含みます。

入出力例

入力 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

出力 1

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$ 時間かかります。

小課題

得点：$300$

問題作成：David Benjamin、Jacob Steinhardt、2008 年