Problem Statement

高橋君はゲーム内で国家を運営している。

国家には $N$ 個の都市と、$M$ 本の道がある。それぞれの道は $2$ つの異なる都市を直接結んでおり、道の途中に他の都市がない。また、どの $2$ つの都市についても、それらの都市を直接結ぶ道は高々 $1$ つである。

最初、どの道も舗装されておらず、どの都市にも交易所が設置されていない。

高橋君は国家の発展のため、道路の舗装および交易所の設置を行うことにした。

どの都市についても以下のいずかの条件が満たされていれば、国家は「良い状態」であると呼ぶことにする。

• その都市には交易所が設置されている。
• その都市には交易所が設置されていないものの、その都市から舗装された道のみを経由して、交易所が設置されている別の都市に移動できる。

都市には $1$ から $N$ まで、道には $1$ から $M$ までの番号がつけられている。都市 $i$ に交易所を設置するのには金貨が $c_i$ 枚必要である。また、道 $i$ を舗装するのには金貨が $r_i$ 枚必要である。

あまり金貨を多く持ち合わせていないので、国家を「良い状態」にするのに必要な金貨の枚数をできるだけ少なくしたい。

必要な金貨の枚数として考えられる最小値を求めるプログラムを作成せよ。

Input

入力は以下の形式で標準入力から与えられる。

N M
c_1
c_2
:
c_N
a_1 b_1 r_1
a_2 b_2 r_2
:
a_M b_M r_M

• $1$ 行目には、$2$ つの整数 $N (2 ≦ N ≦ 100,000)$ と $M (1 ≦ M ≦ 200,000)$ が空白区切りで書かれている。これは、都市が $N$ 個、道が $M$ 本あることを表す。
• $2$ 行目から $N$ 行には、都市に関する情報を表す整数 $c_i (1 ≦ c_i ≦ 1,000,000,000)$ が与えられる。これは、都市 $i$ に交易所を設置するのには金貨が $c_i$ 枚必要であることを表す。
• $N+2$ 行目から $M$ 行には、道に関する情報を表す $3$ つの整数 $a_i$, $b_i (1 ≦ a_i ＜ b_i ≦ N)$, $r_i (1 ≦ r_i ≦ 1,000,000,000)$ が空白区切りで与えられる。これは、道 $i$ は都市 $a_i$ と都市 $b_i$ を端点に持ち、舗装するのにはコスト $r_i$ かかることを表す。

部分点

この問題には部分点が設定されている。

• $N ≦ 8$ かつ $M ≦ 10$ を満たすデータセット $1$ に正解した場合は、$10$ 点が与えられる。
• $N ≦ 12$ かつ $M ≦ 66$ を満たすデータセット $2$ に正解した場合は、上記とは別に $20$ 点が与えられる。
• $N ≦ 3,000$ かつ $M ≦ 6,000$ を満たすデータセット $3$ に正解した場合は、上記とは別に $30$ 点が与えられる。
• 追加制約のないデータセット $4$ に正解した場合は、上記とは別に $40$ 点が与えられる。

Output

国家を「良い状態」にするのにかかるコストの合計値として考えられる最小値を $1$ 行に出力せよ。出力の末尾にも改行を入れること。