import Control.Monad
import Data.Array
main = do
  n <- readLn
  a <- listArray ((1,1),(n,n)) . concat 
    <$> replicateM n (map read . words <$> getLine) 
  print $ if n == 1 
    then 0
    else maybe (-1) sum $ sequence [
      if x > a!(i,j)
        then Just (a!(i,j))
        else Nothing |
      i <- [1..n], j <- [i+1..n],
      let x = minimum [a!(i,k) + a!(k,j) |
                k <- [1..n], k/=i && k/=j],
      x /= a!(i,j)]