let prim a n =
  let d = Array.make n max_int in
  d.(0) <- 0;
  let b = Array.make n false in
  let z = Array.make n (-1) in
  let rec doit () =
    let (_, _, u) =
      Array.fold_left (fun (i, m, u) e ->
        if b.(i) = false && m > e then (i + 1, e, i) else (i + 1, m, u))
        (0, max_int, (-1)) d in
    if u = (-1) then ()
    else begin
      b.(u) <- true;
      for i = 0 to n - 1 do
        if b.(i) = true || a.(u).(i) = max_int || d.(i) <= a.(u).(i) then ()
        else begin
          d.(i) <- a.(u).(i);
          z.(i) <- u;
        end
      done;
      doit ()
    end in
  doit ();
  Array.fold_left (fun (i, sum) e ->
    (i + 1, sum + if e = (-1) then 0 else a.(i).(e)))
    (0, 0) z
  |> snd

let () =
  let n = read_int () in
  let a = Array.make_matrix n n max_int in
  for i = 0 to n - 1 do
    for j = 0 to n - 1 do
      let x = Scanf.scanf " %d" (fun x -> x) in
      if x <> (-1) then a.(i).(j) <- x;
    done
  done;
  prim a n |> Printf.printf "%d\n"