プリム法の応用1 Scala編（paizaランク S 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

連結成分 1、頂点数 N、総辺数 M、重み付き、自己ループなしの無向グラフ G が隣接リストの形で与えられます。

また、G のうち、必ず通らなければならない辺の集合 K が与えられます。

K を通る時の G の最小全域木の辺の重みの総和を計算してください。

入力される値

・ G の頂点数 N

・ G の辺の数 M

・頂点 A_i 、頂点 B_i と、その間の辺 i の重み C_i

・必ず通らなければならない辺の数 K (1 ≦ K ≦ M-1)

・ K 個の辺 u_k, v_k

N M
A_1 B_1 C_1
A_2 B_2 C_2
...
A_M B_M C_M
K
u_1 v_1
u_2 v_2
...
u_K v_K

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力

K を通る時の G の最小全域木の辺の重みの総和を 1 行で出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・ 2 ≦ N ≦ 10000

・ N-1 ≦ M ≦ _NC₂

・ N-1 ≦ M ≦ _NC₂

・ 1 ≦ A_i, B_i ≦ N

・ A_i ≠ B_i

・ 1 ≦ C_{i,j} ≦ 100

・ 1 ≦ K ≦ M-1

・ u_k, v_k ∈ G

・ u_k ≠ v_k

・必ず通らなければならない辺を通っても最小全域木は必ず維持されます。