import Control.Applicative
import Control.Monad.ST
import Control.Monad.State
import Control.Monad
import Data.Array.IO
import Data.List
import Data.Array
import Data.Int
import Data.Maybe
import Debug.Trace
import qualified Data.ByteString.Char8 as BS
import Data.IORef

type Node = Int
type Cost = Int64
type Edge = (Node, Cost)
type Graph = Array Node [Edge]

modifyArray arr i f = readArray arr i >>= \x -> writeArray arr i (f x)
readIntBS = fst . fromJust . BS.readInt

inf = maxBound `div` 2 :: Cost

infixr 1 ?
(?) :: Bool -> (a,a) -> a
(?) b t = (if b then fst else snd) t

main = do
  n <- readLn :: IO Int
  graph <- newArray ((1,1),(n,n)) 0 :: IO (IOUArray (Int,Int) Cost)
  mn <- newArray ((1,1),(n,n)) 0 :: IO (IOUArray (Int,Int) Cost)

  forM_ [1..n] $ \i -> do
    as <- map (fromIntegral . readIntBS) . BS.words <$> BS.getLine :: IO [Cost]
    forM_ (zip [1..n] as) $ \(j,a) -> do
      writeArray graph (i,j) a
      writeArray mn (i,j) a

  failed <- newIORef False :: IO (IORef Bool)

  forM_ [1..n] $ \i -> do
    forM [i+1..n] $ \j -> do
      forM [k | k<-[1..n], k/=i, k/=j] $ \k -> do
        ij <- readArray mn (i,j)
        ikj <- (+) <$> readArray mn (i,k) <*> readArray mn (k,j)
        when (ij==ikj) $ writeArray graph (i,j) inf >> writeArray graph (j,i) inf
        when (ikj<ij) $ writeIORef failed True
               
  readIORef failed >>= \a -> 
    if a then
      print $ -1
    else
      print =<< sum . filter (/=inf) . concat <$> (forM [1..n] $ \i -> forM [i+1..n] $ \j -> readArray graph (i,j))
    
