[ARC029C] 高橋君と国家

题目大意： 高桥君在游戏里运营着自己的国度。 他的国度有N个城市和M条道路。每条道路连结着2个不同的城市，途中没有其他的城市。另外，无论哪2个城市，直接连接这些城市的道路都有1条。 最初，没有铺设任何道路，并且任何城市都没有设置交易所。 高桥为了国度的发展，决定铺设道路和建造交易所。 所有的城市，只要满足以下任一条件，国家就称之为“良好状态”： - 那个城市设有交易所。 - 那个城市虽然没有设置交易所，但是通过从那个城市铺设的道路可以移动到设置交易所的其他城市。 城市的编号从1到N，街道的编号为1到M。在城市i设置交易所需要Ci枚金币，铺设道路i需要Ri枚金币。 因为没带太多金币，所以高桥君想尽可能减少把国家变成“良好状态”所必要的金币的枚数。 写一个程序，输出必要的金币枚数的最小值。

[problemUrl]: https://atcoder.jp/contests/arc029/tasks/arc029_3 高橋君はゲーム内で国家を運営している。 国家には $ 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 $ かかることを表す。

国家を「良い状態」にするのにかかるコストの合計値として考えられる最小値を $ 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

350

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

150

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

160

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 8 $ かつ $ M\ ≦\ 10 $ を満たすデータセット $ 1 $ に正解した場合は、$ 10 $ 点が与えられる。 - $ N\ ≦\ 12 $ かつ $ M\ ≦\ 66 $ を満たすデータセット $ 2 $ に正解した場合は、上記とは別に $ 20 $ 点が与えられる。 - $ N\ ≦\ 3,000 $ かつ $ M\ ≦\ 6,000 $ を満たすデータセット $ 3 $ に正解した場合は、上記とは別に $ 30 $ 点が与えられる。 - 追加制約のないデータセット $ 4 $ に正解した場合は、上記とは別に $ 40 $ 点が与えられる。 ### Sample Explanation 1 都市と道の配置は下図のようになっています。 !\[\](/img/arc/029/3-1.png) 以下の条件で交易所の設置および道の舗装をします。 - 都市 $ 1 $ に交易所を設置する。交易所の設置には金貨が $ 40 $ 枚必要である。 - 都市 $ 3 $ に交易所を設置する。交易所の設置には金貨が $ 30 $ 枚必要である。 - 都市 $ 5 $ に交易所を設置する。交易所の設置には金貨が $ 70 $ 枚必要である。 - 道 $ 1 $ (都市 $ 1 $ と都市 $ 2 $ を結ぶ) を舗装する。舗装には金貨が $ 40 $ 枚必要である。 - 道 $ 3 $ (都市 $ 1 $ と都市 $ 4 $ を結ぶ) を舗装する。舗装には金貨が $ 60 $ 枚必要である。 - 道 $ 7 $ (都市 $ 5 $ と都市 $ 6 $ を結ぶ) を舗装する。舗装には金貨が $ 60 $ 枚必要である。 - 道 $ 8 $ (都市 $ 6 $ と都市 $ 7 $ を結ぶ) を舗装する。舗装には金貨が $ 50 $ 枚必要である。 最終的な都市と道の状態は下図のようになります。ここでは、交易所が設置されている都市の枠を二重に、舗装された道を二重線にして表示してあります。 !\[\](/img/arc/029/3-2.png) この場合、国家は「良い状態」といえます。実際、 - 都市 $ 1 $ には交易所が設置されている。 - 都市 $ 2 $ には交易所が設置されていないが、舗装されている道 $ 1 $ を経由して、交易所が設置されている都市 $ 1 $ に移動することができる。 - 都市 $ 3 $ には交易所が設置されている。 - 都市 $ 4 $ には交易所が設置されていないが、舗装されている道 $ 3 $ を経由して、交易所が設置されている都市 $ 1 $ に移動することができる。 - 都市 $ 5 $ には交易所が設置されている。 - 都市 $ 6 $ には交易所が設置されていないが、舗装されている道 $ 7 $ を経由して、交易所が設置されている都市 $ 5 $ に移動することができる。 - 都市 $ 7 $ には交易所が設置されていないが、舗装されている道 $ 7 $ と舗装されている道 $ 8 $ を経由して、交易所が設置されている都市 $ 5 $ に移動することができる。 となっています。金貨は $ 40\ +\ 30\ +\ 70\ +\ 40\ +\ 60\ +\ 60\ +\ 50\ =\ 350 $ 枚必要となります。 ### Sample Explanation 2 すべての都市に交易所を設置する方が安上がりです。