import Data.Array.IO
import Data.List
import Control.Monad

type Memo = IOUArray (Int, Int) Int
type Road = IOUArray (Int, Int) Bool

main = do
  n <- readLn :: IO Int
  input <- concat . map (map read . words) . lines <$> getContents :: IO [Int]
  let index = [(i, j, k) | i <- [1..n], j <- [1..n], k <- [1..n], i /= j, j /= k, k /= i]
  memo <- newListArray ((1, 1), (n, n)) input :: IO (IOUArray (Int, Int) Int)
  road <- newArray ((1, 1), (n, n)) True :: IO (IOUArray (Int, Int) Bool)
  memo' <- foldM (memoizeWF road) memo index
  ans <- getElems memo'
  if input /= ans then putStrLn "-1"
                  else do
                    necessary <- getElems road
                    print $ flip div 2 . sum $ zipWith (\x y -> if x then y else 0) necessary ans

memoizeWF :: Road -> Memo -> (Int, Int, Int) -> IO (IOUArray (Int, Int) Int)
memoizeWF road memo (i, j, k) = do
  b <- readArray road (i, j)
  x <- readArray memo (i, j)
  y <- readArray memo (i, k)
  z <- readArray memo (k, j)
  let minWeight = min x $ y + z
  writeArray road (i, j) $ b && x < y + z
  writeArray memo (i, j) minWeight
  return memo