問題描述 Farmer John變得非常懶，他不想再繼續(xù)維護(hù)供奶牛之間供通行的道路。道路被用來連接N個牧場，牧場被連續(xù)地編號為1到N。每一個牧場都是一個奶牛的家。FJ計劃除去P條道路中盡可能多的道路，但是還要保持牧場之間 的連通性。你首先要決定那些道路是需要保留的N-1條道路。第j條雙向道路連接了牧場Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej)，而且走完它需要Lj的時間。沒有兩個牧場是被一條以上的道路所連接。奶牛們非常傷心，因?yàn)樗齻兊慕煌ㄏ到y(tǒng)被削減了。你需要到每一個奶牛的住處去安慰她們。每次你到達(dá)第i個牧場的時候(即使你已經(jīng)到過)，你必須花去Ci的時間和奶牛交談。你每個晚上都會在同一個牧場(這是供你選擇的)過夜，直到奶牛們都從悲傷中緩過神來。在早上 起來和晚上回去睡覺的時候，你都需要和在你睡覺的牧場的奶牛交談一次。這樣你才能完成你的 交談任務(wù)。假設(shè)Farmer John采納了你的建議，請計算出使所有奶牛都被安慰的最少時間。

輸入格式 第1行包含兩個整數(shù)N和P。

接下來N行，每行包含一個整數(shù)Ci。

接下來P行，每行包含三個整數(shù)Sj, Ej和Lj。

輸出格式 輸出一個整數(shù), 所需要的總時間(包含和在你所在的牧場的奶牛的兩次談話時間)。 樣例輸入 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 樣例輸出 176 數(shù)據(jù)規(guī)模與約定 5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000。