隣接リストから最小全域木を求める Python2編（paizaランク A 相当）

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

問題

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

頂点 A_i と頂点 B_i の間には、重み C_i の辺 i があります。

G に対する最小全域木の辺の重みの総和を出力してください。

入力される値

・ G の頂点数 N

・ G の辺の数 M

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

N M
A_1 B_1 C_1
A_2 B_2 C_2
...
A_M B_M C_M

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

期待する出力

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

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

条件

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

・ 2 ≦ N ≦ 1000

・ N-1 ≦ M ≦ _NC₂

・ 1 ≦ A_i, B_i ≦ N

・ A_i ≠ B_i

・ 1 ≦ C_{i,j} ≦ 100