import scala.io.StdIn.{readInt, readLine};
import scala.annotation.tailrec;
object Main {
    def main(args: Array[String]): Unit = {
        val size = readInt;
        val m = new Array[Array[Int]](size);
        (0 until size).foreach {  i => m(i) = readLine.trim.split(" ").map( a => if (a.toInt == -1) Int.MaxValue else a.toInt)}
        val g = new Graph(size, m);
        val (parent, distance) = g.prim;
        println(distance.sum)
    }
}
case class Graph(size: Int, matrix: Array[Array[Int]]) {
    val INFINITY = Int.MaxValue
    def prim(): (Array[Int], Array[Int]) = {
        // WHITE : 未訪問, GRAY: MST候補ノード, BLACK: MST追加済みノード
        val WHITE = 0; val GRAY = 1; val BLACK = 2;
        val color = new Array[Int](size); // 訪問状態リスト(WHITE, GRAY, BLACK)
        val distance = new Array[Int](size).map( e => INFINITY); //  重みリスト
        val parents = new Array[Int](size); //  親ノードリスト
        @tailrec
        def _prim(curr: Int): Unit = {
            // MSTに属する頂点の集合から最も近いノードの index を取得する
            val idx = (0 until size).foldLeft(-1) { (minidx, i) =>
                if (color(i) != BLACK) {
                    // curr の子ノードをMST候補ノードに追加
                    if (matrix(curr)(i) != -1) {
                        color(i) = GRAY;
                    }
                    if (color(i) == GRAY) {
                        // すでに登録されている重みよりも curr からの重みのほうが小さい場合は
                        // 親ノードと重みを更新する
                        if (matrix(curr)(i) < distance(i)) {
                            distance(i) = matrix(curr)(i);
                            parents(i) = curr;
                        }
                        if (minidx == -1 || distance(i) < distance(minidx)) i else minidx;
                    } else { // color(i) == WHITE
                        // 現時点のMSTに隣接していないノードは評価しない
                        minidx;
                    }
                } else { // color(i) == BLACK 
                    // すでにMSTに追加されているノードは評価しない
                    minidx;
                }
            }
            if (idx != -1){
                // MSTから最も距離の近いノードを追加
                color(idx) = BLACK;
                _prim(idx);
            }
        }
        distance(0) = 0;
        parents(0) = -1;
        color(0) = BLACK;
        _prim(0);
        (parents, distance);
    }
}
