C - 高橋君と国家 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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

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

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

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

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

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

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

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

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

入力

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

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 点が与えられる。

出力

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

入力例1

7 8
40
50
30
70
70
80
80
1 2 40
1 3 50
1 4 60
2 5 90
3 4 80
4 5 110
5 6 60
6 7 50

出力例1

350

都市と道の配置は下図のようになっています。

以下の条件で交易所の設置および道の舗装をします。

  • 都市 1 に交易所を設置する。交易所の設置には金貨が 40 枚必要である。
  • 都市 3 に交易所を設置する。交易所の設置には金貨が 30 枚必要である。
  • 都市 5 に交易所を設置する。交易所の設置には金貨が 70 枚必要である。
  • 道 1 (都市 1 と都市 2 を結ぶ) を舗装する。舗装には金貨が 40 枚必要である。
  • 道 3 (都市 1 と都市 4 を結ぶ) を舗装する。舗装には金貨が 60 枚必要である。
  • 道 7 (都市 5 と都市 6 を結ぶ) を舗装する。舗装には金貨が 60 枚必要である。
  • 道 8 (都市 6 と都市 7 を結ぶ) を舗装する。舗装には金貨が 50 枚必要である。

最終的な都市と道の状態は下図のようになります。ここでは、交易所が設置されている都市の枠を二重に、舗装された道を二重線にして表示してあります。

この場合、国家は「良い状態」といえます。実際、

  • 都市 1 には交易所が設置されている。
  • 都市 2 には交易所が設置されていないが、舗装されている道 1 を経由して、交易所が設置されている都市 1 に移動することができる。
  • 都市 3 には交易所が設置されている。
  • 都市 4 には交易所が設置されていないが、舗装されている道 3 を経由して、交易所が設置されている都市 1 に移動することができる。
  • 都市 5 には交易所が設置されている。
  • 都市 6 には交易所が設置されていないが、舗装されている道 7 を経由して、交易所が設置されている都市 5 に移動することができる。
  • 都市 7 には交易所が設置されていないが、舗装されている道 7 と舗装されている道 8 を経由して、交易所が設置されている都市 5 に移動することができる。

となっています。金貨は 40 + 30 + 70 + 40 + 60 + 60 + 50 = 350 枚必要となります。

入力例2

3 3
50
50
50
1 2 60
1 3 60
2 3 60

出力例2

150

すべての都市に交易所を設置する方が安上がりです。

入力例3

5 7
80
70
60
50
40
1 3 20
1 4 70
1 5 30
2 3 30
2 4 90
3 4 40
4 5 80

出力例3

160