Scanf.scanf "%d" (fun n ->
    let a = Array.init n (fun _ ->
        Array.init n (fun _ -> Scanf.scanf " %d" (fun i -> i)))
    in
    let nei = Array.make n [] in
    for i = 0 to n - 1 do
        for j = i + 1 to n - 1 do
            let rec loop k =
                if k = n then true else
                    if k = i || k = j then loop (k + 1) else
                        if a.(i).(j) >= a.(i).(k) + a.(k).(j) then false else
                            loop (k + 1)
            in
            if loop 0 then (
                nei.(i) <- (j, a.(i).(j)) :: nei.(i);
                nei.(j) <- (i, a.(i).(j)) :: nei.(j)
            )
        done
    done;
    let mat = Array.make_matrix n n (max_int / 1000) in
    for i = 0 to n - 1 do mat.(i).(i) <- 0 done;
    Array.iteri (fun i l ->
        List.iter (fun (j, len) -> mat.(i).(j) <- len) l) nei;
    for k = 0 to n - 1 do
        for i = 0 to n - 1 do
            for j = 0 to n - 1 do
                mat.(i).(j) <- min mat.(i).(j) (mat.(i).(k) + mat.(k).(j));
            done
        done
    done;
    let rec loop_i i =
        let rec loop_j j =
            if j = n then true else
                if a.(i).(j) <> mat.(i).(j) then false else
                    loop_j (j + 1)
        in
        if i = n then true else
            if loop_j 0 then loop_i (i + 1) else false
    in
    Printf.printf "%d\n" @@ 
        if loop_i 0 then
            let len = Array.fold_left (List.fold_left (fun acc (_, len) -> acc + len)) 0 nei in
            len / 2
        else -1
)