Farmer John 太懶，不想維護目前能到達全部 $N$ 個牧場（$5\le N\le10{,}000$，編號 $1\ldots N$）的牛路。每牧場恰一頭牛。他計畫保持連通並盡量移除 $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$）。每對牧場直接道路至多一條。
交通系統縮減令牛傷心。你每天至少拜訪每頭牛一次讓她開心。每次訪問牧場 $i$（即使只是路過），須花 $C_i$ 時間（$1\le C_i\le1{,}000$）與牛交談。
直到牛恢復心情，你每晚在自己選定的同一牧場睡覺，至少早晨醒來、傍晚回去睡覺時，都要與那裡的牛交談。
假定 FJ 按你建議保留道路，且你選最佳睡覺牧場，求每天拜訪每頭牛至少一次的最少總時間。
前 $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$ 行：一整數，拜訪全部牛的總時間，包括對睡覺牧場牛的兩次拜訪。
範例
輸入格式 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 年