
open Scanf
open Printf

let flip f x y = f y x

let range a b =
  let rec f acc a b = if a > b then acc else f (b::acc) a (b-1) in
  f [] a (b-1)

let read_int () = scanf " %d" (fun x -> x)
let rec read_ints n = Array.init n (fun _ -> read_int ())

let rec for_iter a b f = if a >= b then [] else let x = f a in x :: for_iter (a+1) b f
let rec for_iter_ a b f = if a >= b then () else (f a; for_iter_ (a+1) b f)
let rec for_all_iter a b f = if a >= b then true else f a && for_all_iter (a+1) b f

let inf = 20202020202020

let () =
  let n = read_int () in
  let mtx = Array.init n (fun _ -> read_ints n) in

  let mtx' = Array.init n (fun i -> Array.copy mtx.(i)) in
  for_iter_ 0 n (fun k -> for_iter_ 0 n (fun i -> for_iter_ 0 n (fun j ->
    mtx'.(i).(j) <- min mtx'.(i).(j) (mtx'.(i).(k) + mtx'.(k).(j)))));

  let valid = for_all_iter 0 n (fun i ->
    for_all_iter 0 n (fun j ->
      mtx.(i).(j) = mtx'.(i).(j))) in
  if not valid then (print_endline "-1"; exit 0);

  let edges =
    let res = Array.make (n*(n-1)/2) (-1,-1,-1) in
    let rec f i a b =
      if a >= n then ()
      else if b >= n then f i (a+1) (a+2)
      else (res.(i) <- (a, b, mtx.(a).(b)); f (i+1) a (b+1)) in
    f 0 0 1;
    Array.sort (fun (_,_,w0) (_,_,w1) -> w0-w1) res;
    res in

  for_iter_ 0 n (fun j ->
    for_iter_ 0 n (fun k -> mtx'.(j).(k) <- inf);
    mtx'.(j).(j) <- 0);
  Array.fold_left (fun s (u, v, w) ->
    if mtx'.(u).(v) <= w then s
    else (
      mtx'.(u).(v) <- w; mtx'.(v).(u) <- w;
      for_iter_ 0 n (fun j -> for_iter_ 0 n (fun k ->
        mtx'.(j).(k) <- min mtx'.(j).(k) (mtx'.(j).(u) + w + mtx'.(v).(k));
        mtx'.(j).(k) <- min mtx'.(j).(k) (mtx'.(j).(v) + w + mtx'.(u).(k))));
      s+w)) 0 edges
  |> printf "%d\n"
