let () = Scanf.scanf "%d\n" @@ fun n ->
  let d =
    Array.init n @@ fun _ ->
      Array.init n @@ fun _ ->
        Scanf.scanf "%d " @@ fun a -> a in
  try
    for i = 0 to n - 1 do
      for j = 0 to n - 1 do
        for k = 0 to n - 1 do
          if d.(j).(i) + d.(i).(k) < d.(j).(k) then raise Not_found
        done
      done
    done;
    let d' = Array.make_matrix n n 300000000000 in
    begin
      List.concat @@ Array.to_list @@ Array.mapi (fun i d ->
        Array.to_list @@ Array.mapi (fun j d -> (i, j, d)) d) d
    end
    |> List.sort (fun (_, _, d) (_, _, d') -> compare d d')
    |> List.fold_left (fun acc (i, j, d) ->
        if d'.(i).(j) <= d
        then acc
        else begin
          d'.(i).(j) <- d;
          d'.(j).(i) <- d;
          for k = 0 to n - 1 do
            for l = 0 to n - 1 do
              if d'.(k).(i) + d + d'.(j).(l) < d'.(k).(l) then
                d'.(k).(l) <- d'.(k).(i) + d + d'.(j).(l);
              if d'.(k).(j) + d + d'.(i).(l) < d'.(k).(l) then
                d'.(k).(l) <- d'.(k).(j) + d + d'.(i).(l)
            done
          done;
          d + acc
        end) 0
    |> Printf.printf "%d\n"
  with Not_found -> print_endline "-1"