最小全域木

与えられた重み付きグラフ $G = (V, E)$ に対する最小全域木の辺の重みの総和を計算するプログラムを作成してください。

入力

最初の行に $G$ の頂点数 $n$ が与えられます。続く $n$ 行で $G$ を表す $n \times n$ の隣接行列 $A$ が与えられます。$A$ の要素 $a_{ij}$ は、頂点 $i$ と頂点 $j$ を結ぶ辺の重みを表します。ただし、辺がなければ-1 で示されます。

出力

$G$ の最小全域木の辺の重みの総和を１行に出力してください。

制約

• $1 \leq n \leq 100$
• $0 \leq a_{ij} \leq 2,000$ ($a_{ij} \neq -1$ のとき)
• $a_{ij} = a_{ji}$
• グラフ $G$ は連結である。

入力例 1

5
 -1 2 3 1 -1
 2 -1 -1 4 -1
 3 -1 -1 1 1
 1 4 1 -1 3
 -1 -1 1 3 -1

出力例 1

5

参考文献

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

---