{-# 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 -- calc (V.length vs) 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 [] (fromList es)) --popLoop [] (fromList es))
    where
        n = V.length vs
        newVec :: ST s (MV2 s Bool)
        newVec = VM.replicateM n $ VM.replicate n False

        popLoop :: [Edge] -> Heap Edge -> MV2 s Bool -> ST s (Bool, [Edge])
        popLoop acc (pop -> Just (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
        
        {-
        newVec :: ST s (VM.STVector s Bool)
        newVec = V.unsafeThaw . V.fromListN (V.length vs) $ True : repeat False
        popLoop :: [Edge] -> Heap Edge -> VM.STVector s Bool -> ST s (Bool, [Edge])
        popLoop acc (pop -> Just (e, h)) fs
            | (vs `at` (0, to e)) > (vs `at` (0, from e)) + weight e = return (False, acc)
            | (vs `at` (0, to e)) == (vs `at` (0, from e)) + weight e = VM.unsafeRead fs (to e) >>= checkFlag
            | otherwise = popLoop acc h fs 
            where
                checkFlag f
                    | f = popLoop acc h fs
                    | otherwise = VM.unsafeWrite fs (to e) True >> popLoop (e : acc) h fs
        popLoop acc _ _ = return (True, acc)
        -}

calc :: Int -> [Edge] -> Int

calc n es = runST (makeTreeM n >>= calcST)
    where
        calcST :: UFTree s -> ST s Int
        calcST uft = popLoop 0 $ fromList es
            where
                popLoop acc (pop -> Just (e, hs)) = isSameM (from e) (to e) uft >>= checkUnion
                    where
                        checkUnion b
                            | b = popLoop acc hs
                            | otherwise = unionNodesM (from e) (to e) uft >> popLoop (acc + weight e) hs
                popLoop acc _ = return acc

newtype UFTree s = UFTree (VM.MVector s (Int, Int))

makeTreeM :: (PrimMonad m) => Int -> m (UFTree (PrimState m))
makeTreeM n = UFTree <$> V.unsafeThaw vec
    where
        vec = V.fromListN n $ zip (repeat 0) [0..]

findRootM :: (PrimMonad m) => Int -> UFTree (PrimState m) -> m Int
findRootM v t@(UFTree vs) = VM.unsafeRead vs v >>= checkRoot
    where
        checkRoot (_, root)
            | v == root = return v
            | otherwise = findRootM root t
            
unionNodesM :: (PrimMonad m) => Int -> Int -> UFTree (PrimState m) -> m ()
unionNodesM a b t@(UFTree vs) = mapM (flip findRootM t) [a, b] >>= checkRoot
    where
        checkRoot [c, d]
            | c == d = return ()
            | otherwise = mapM (VM.unsafeRead vs) [c, d] >>= checkRank c d 
        checkRank c d [ra, rb]
            | ra < rb = VM.unsafeModify vs (second (const d)) c
            | ra > rb = VM.unsafeModify vs (second (const c)) d
            | otherwise = VM.unsafeModify vs (\(x, _) -> (x + 1, c)) d
            
isSameM :: (PrimMonad m) => Int -> Int -> UFTree (PrimState m) -> m Bool
isSameM a b t = (==) <$> findRootM a t <*> findRootM b t

data Heap a = E | T Int a (Heap a) (Heap a)
    deriving (Show)
    
empty :: Heap a 
empty = E

null :: Heap a -> Bool 
null E = True
null _ = False

merge :: (Ord a) => Heap a -> Heap a -> Heap a
merge lh@(T _ lv la lb) rh@(T _ rv ra rb)
    | lv <= rv = makeT lv la $ merge lb rh
    | otherwise = makeT rv ra $ merge lh rb
    where
        makeT v a b
            | rank a >= rank b = T (rank b + 1) v a b
            | otherwise = T (rank a + 1) v b a
        rank (T r _ _ _) = r
        rank _ = 0
        
merge lh E = lh
merge _ rh = rh

push :: (Ord a) => a -> Heap a -> Heap a
push x = merge (T 1 x E E)

pop :: (Ord a) => Heap a -> Maybe (a, Heap a) 
pop (T _ x a b) = Just (x, merge a b)
pop _ = Nothing

fromList :: (Ord a) => [a] -> Heap a
fromList = br . fmap (\x -> T 1 x E E)
    where
        build (x : y : zs) = merge x y : build zs
        build xs = xs
        br [x] = x
        br xs = br $ build xs

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