let prim a n =
  let d = Array.make n max_int in
  let z = Array.make n (-1) in
  let b = Array.make n false in
  let rec dudu i m u =
    if i = n then u
    else if b.(i) = false && m > d.(i) then dudu (i + 1) d.(i) i
    else dudu (i + 1) m u
  and wa j u =
    if j < n then begin
      if b.(j) = false && a.(u).(j) <> max_int && d.(j) > a.(u).(j) then begin
        d.(j) <- a.(u).(j);
        z.(j) <- u
      end;
      wa (j + 1) u
    end
  and doit () =
    let u = dudu 0 max_int (-1) in
    if u <> (-1) then (b.(u) <- true; wa 0 u; doit ())
  in
  d.(0) <- 0;
  doit ();
  let rec sum i acc =
    if i = n then acc
    else sum (i + 1) (acc + (if z.(i) <> (-1) then a.(i).(z.(i)) else 0))
  in
  sum 0 0

let () =
  let n = read_int () in
  let a = Array.make_matrix n n max_int in
  let rec read i =
    if i < n then
      let rec aux j =
        if j < n then begin
          let x = Scanf.scanf " %d " (fun x -> x) in
          if x <> (-1) then a.(i).(j) <- x;
          aux (j + 1)
        end
      in
      aux 0;
      read (i + 1)
  in
  read 0;
  Printf.printf "%d\n" (prim a n)