とある海域に，ミスト諸島と呼ばれる美しい自然と豊かな資源に恵まれた島々がある．
気候も温暖であるため，人々はそこで長きに渡って平和な暮らしを営んできた．
しかし，最近になって大変な事実が判明した．
地殻変動によって，ミスト諸島の島々が遠からず沈没してしまうというのだ．
この事態に対応するため，各島の代表からなる対策本部が結成された．
まず，調査隊の働きにより各島がいつ沈没してしまうかが明らかになった．
また，ミスト諸島の技術を結集することで，いくつかの島の間には橋が架けられることも分かった．
その結果，島の間に橋を架け，各島の住民が特定の島に避難できるようにすることに決まった．
現段階で，どの島を避難先にするかは決まっていないらしい．
そのため，最初はどの島が避難先になっても良いよう，どの島からもいくつかの橋を渡ることで他の全ての島に行けるように橋を架ける．
時間の経過によって島が沈んだとき，両端の島が一方でも沈んだ橋は通行できなくなる．
このとき，最初の橋の架け方によっては，ある島から辿りつけないような島ができてしまう場合がある．
この場合は，新たに橋を架けることで，まだ沈んでいない島々の間で移動経路が確保できるようにする．
どのように橋を架けても移動経路が確保できなくなった場合は，それ以上の橋の建設は行わない．
対策本部は，それまでに避難先を決め，住民の避難を完了させなくてはならないだろう．
なお，現時点で既に移動経路を確保するように橋を架ける事が出来ない場合は，橋の建設は一切行わない．
対策本部は新たな案を練ることになるだろう．
ところで，橋は架ける位置によって建設費用が決まっている． 避難には何かと費用がかかるので，対策本部では橋の建設費用の合計がなるべく小さくなるように橋を架けたいと考えているようだ． そのためにはどのように橋を架ければ良いだろうか．
入力は複数のデータセットから構成される．各データセットの形式は次の通りである．
N M h1 h2 ... hN a1 b1 c1 a2 b2 c2 ... aM bM cM
N は島の数を表す整数であり，2 以上 200 以下と仮定して良い．
また，各島には 1 から N の数字が割り振られている．
M は橋を建設できる島のペアの数を表す 1 以上の整数である．
続く N 行には各島がいつ沈没するかを示す情報が与えられる．
hi は島 i が hi 日後に沈むという事を表す整数であり，1 以上 1,000,000 以下と仮定して良い．
同時に複数の島が沈む場合もある．
続く M 行は建設できる橋の情報を表す．
各行はスペースで区切られた 3 つの整数を含み，ai と bi が橋の両端の島の番号，ci が橋の建設費用である(1 ≤ i ≤ M)．
各橋の建設費用は 1 以上 1,000,000 以下と仮定して良い．
ある 2 つの島を結ぶ橋が 2 つ以上与えられる事や，橋の両端が同じ島である事はない．
N=M=0 は入力の終わりを示す．これはデータセットには含めない．
各データセットに対し，条件に従って橋を建設するときの最小の合計費用を求め，それぞれ1行に出力しなさい．
3 3 1 2 3 1 2 1 1 3 1 2 3 10 3 2 100 10000 1000000 1 2 2 1 3 3 6 6 2 3 5 7 11 13 1 3 17 3 5 19 5 1 23 2 4 29 4 6 31 6 2 37 11 16 74 25 3 39 55 18 74 55 74 3 18 1 7 200 9 1 423 2 9 205 6 2 255 2 5 123 4 2 193 2 3 200 10 2 333 2 11 256 3 10 171 4 10 512 1 2 201 8 5 314 6 7 150 11 6 257 7 9 315 20 38 412516 185397 509168 712745 966959 101213 666120 790528 275431 677098 623178 240167 4371 299088 925699 72800 121416 796859 810604 142754 13 5 1000000 3 7 991832 10 1 781938 15 8 455731 1 3 655887 1 20 604802 19 10 452912 15 5 360121 10 15 256967 9 5 682599 8 7 917302 5 18 974821 2 19 790778 17 5 298105 15 11 132405 18 19 745543 2 4 790778 1 2 790778 11 14 269668 15 4 882901 1 14 522591 15 18 424799 9 19 712540 20 5 592132 18 17 770826 19 8 592380 16 5 258739 8 4 794157 3 18 569611 7 19 340021 19 11 803293 8 18 692318 9 6 626882 20 2 592133 2 17 196463 12 14 506077 16 20 928375 12 18 894053 0 0
11 5 0 2013 9658580