隣接行列から最小全域木を求める C編（paizaランク B 相当）

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

問題

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

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

入力される値

・ G の頂点数 N

・ G の各辺間の重み C_{i,j} (1 ≦ i, j ≦ N)

・ C_{i,j} は頂点 i - j の間の辺の重みであり、i - j 間に辺が存在しない場合は 0 が与えられます。

N
C_{1,1} C_{1,2} ... C_{1,N}
C_{2,1} C_{2,2} ... C_{2,N}
...
C_{N,1} C_{N,2} ... C_{N,N}

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

期待する出力

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

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

条件

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

・ 2 ≦ N ≦ 100

・ 1 ≦ i, j ≦ N

・ 1 ≦ C_{i,j} ≦ 100 または C_{i,j} = 0