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.Word
import Data.Maybe
import Debug.Trace

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

modifyArray arr i f = readArray arr i >>= \x -> writeArray arr i (f x)

inf = maxBound `div` 2 :: Cost

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 read . words <$> getLine :: IO [Cost]
    forM_ (zip [1..n] as) $ \(j,a) -> do
      writeArray graph (i,j) a
      writeArray mn (i,j) a

  ans <- or <$> (forM [1..n] $ \i -> do
             or <$> (forM [i+1..n] $ \j -> do
                 any isNothing <$>
                   (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
                       return $ if ikj < ij then Nothing else Just ()
                   )
               )
         )

  if ans then
    print $ -1
    else
    print =<< sum . filter (/=inf) . concat <$> (forM [1..n] $ \i -> forM [i+1..n] $ \j -> readArray graph (i,j))
