{-# LANGUAGE ViewPatterns #-}
import Control.Arrow
import Control.Monad
import Control.Monad.Primitive
import Control.Monad.ST
import Data.List
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import Data.Ord
import Debug.Trace 
main :: IO ()
main = readLn >>= readContents >>= print . solve . build

type V2 a = V.Vector (V.Vector a)
type MV2 s a = VM.STVector s (VM.STVector s a)

readM :: MV2 s a -> (Int, Int) -> ST s a
readM vs (x, y) = VM.unsafeRead vs x >>= (\xs -> VM.unsafeRead xs y)

writeM :: MV2 s a -> (Int, Int) -> a -> ST s ()
writeM vs (x, y) v = VM.unsafeRead vs x >>= (\xs -> VM.unsafeWrite xs y v)

modifyM :: MV2 s a -> (a -> a) -> (Int, Int) -> ST s ()
modifyM vs f (x, y) = VM.unsafeRead vs x >>= (\xs -> VM.unsafeModify xs f y)

at :: V2 a -> (Int, Int) -> a
at vs (x, y) = vs V.! x V.! y

data Edge = Edge {from :: Int, to :: Int, weight :: Int}
    deriving (Show, Eq)

instance Ord Edge where
    compare = comparing weight

build :: [[Int]] -> V2 Int
build = V.fromList . map V.fromList

solve :: V2 Int -> Int
solve vs 
    | b = (`div` 2) . sum $ map weight $ traceShowId es
    | otherwise = -1
    where
        (b, es) = check vs $ edges vs

edges :: V2 Int -> [Edge]
edges vs = map makeEdge [(x, y) | x <- [0..n], y <- [0..n], x /= y]
    where
        n = V.length vs - 1
        makeEdge (x, y) = Edge {from = x, to = y, weight = vs `at` (x, y)}

check :: V2 Int -> [Edge] -> (Bool, [Edge])
check vs es = runST (newVec >>= popLoop [] (sort es))
    where
        n = V.length vs
        newVec :: ST s (MV2 s Bool)
        newVec = VM.replicateM n $ VM.replicate n False

        popLoop :: [Edge] -> [Edge] -> MV2 s Bool -> ST s (Bool, [Edge])
        popLoop acc (e : h) fs = innerLoop True acc e h fs [0..(n - 1)]
        popLoop acc _ _ = return (True, acc)
        
        innerLoop a acc e h fs (i : xs)
            | (vs `at` (i, to e)) > (vs `at` (i, from e)) + weight e = return (False, acc)
            | (vs `at` (i, to e)) == (vs `at` (i, from e)) + weight e = readM fs (i, to e) >>= checkFlag
            | otherwise = innerLoop a acc e h fs xs
            where
                checkFlag b
                    | b = innerLoop a acc e h fs xs
                    | a = writeM fs (i, to e) True >> innerLoop False (e : acc) e h fs xs
                    | otherwise = writeM fs (i, to e) True >> innerLoop a acc e h fs xs
        innerLoop _ acc _ h fs _ = popLoop acc h fs

readLine :: IO [Int]
readLine = unfoldr (\s -> second (maybe B.empty snd . B.uncons) <$> B.readInt s) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine