沈みゆく島

とある海域に，ミスト諸島と呼ばれる美しい自然と豊かな資源に恵まれた島々がある． 気候も温暖であるため，人々はそこで長きに渡って平和な暮らしを営んできた． しかし，最近になって大変な事実が判明した． 地殻変動によって，ミスト諸島の島々が遠からず沈没してしまうというのだ．

この事態に対応するため，各島の代表からなる対策本部が結成された． まず，調査隊の働きにより各島がいつ沈没してしまうかが明らかになった． また，ミスト諸島の技術を結集することで，いくつかの島の間には橋が架けられることも分かった． その結果，島の間に橋を架け，各島の住民が特定の島に避難できるようにすることに決まった．

現段階で，どの島を避難先にするかは決まっていないらしい． そのため，最初はどの島が避難先になっても良いよう，どの島からもいくつかの橋を渡ることで他の全ての島に行けるように橋を架ける． 時間の経過によって島が沈んだとき，両端の島が一方でも沈んだ橋は通行できなくなる． このとき，最初の橋の架け方によっては，ある島から辿りつけないような島ができてしまう場合がある． この場合は，新たに橋を架けることで，まだ沈んでいない島々の間で移動経路が確保できるようにする． どのように橋を架けても移動経路が確保できなくなった場合は，それ以上の橋の建設は行わない． 対策本部は，それまでに避難先を決め，住民の避難を完了させなくてはならないだろう． なお，現時点で既に移動経路を確保するように橋を架ける事が出来ない場合は，橋の建設は一切行わない． 対策本部は新たな案を練ることになるだろう．

ところで，橋は架ける位置によって建設費用が決まっている． 避難には何かと費用がかかるので，対策本部では橋の建設費用の合計がなるべく小さくなるように橋を架けたいと考えているようだ． そのためにはどのように橋を架ければ良いだろうか．

Input

入力は複数のデータセットから構成される．各データセットの形式は次の通りである．

N M
h1
h2
...
hN
a1 b1 c1
a2 b2 c2
...
aM bM cM

N は島の数を表す整数であり，2 以上 200 以下と仮定して良い． また，各島には 1 から N の数字が割り振られている． M は橋を建設できる島のペアの数を表す 1 以上の整数である．

続く N 行には各島がいつ沈没するかを示す情報が与えられる． h_i は島 i が h_i 日後に沈むという事を表す整数であり，1 以上 1,000,000 以下と仮定して良い． 同時に複数の島が沈む場合もある．

続く M 行は建設できる橋の情報を表す． 各行はスペースで区切られた 3 つの整数を含み，a_i と b_i が橋の両端の島の番号，c_i が橋の建設費用である(1 ≤ i ≤ M)． 各橋の建設費用は 1 以上 1,000,000 以下と仮定して良い． ある 2 つの島を結ぶ橋が 2 つ以上与えられる事や，橋の両端が同じ島である事はない．

N=M=0 は入力の終わりを示す．これはデータセットには含めない．

Output

各データセットに対し，条件に従って橋を建設するときの最小の合計費用を求め，それぞれ1行に出力しなさい．

Sample Input

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

Output for Sample Input

11
5
0
2013
9658580