{-# 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

main :: IO ()
main = readLn >>= readContents >>= solve . build >>= print

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

readM :: (PrimMonad m) => MV2 (PrimState m) a -> (Int, Int) -> m a
readM vs (x, y) = VM.unsafeRead vs x >>= (\xs -> VM.unsafeRead xs y)

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

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)

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

solve :: V2 Int -> IO Int
solve vs = newVec >>= (\xs -> check vs xs idxs)
    where
        n = V.length vs - 1
        idxs = (,) <$> [0..n] <*> sortBy (comparing weight) [makeEdge x y | x <- [0..n], y <- [0..n], x /= y]
        makeEdge x y = Edge {from = x, to = y, weight = vs `at` (x, y)}
        newVec = (,) <$> (VM.replicateM (n + 1) $ VM.replicate (n + 1) False) <*> (VM.replicateM (n + 1) $ VM.replicate (n + 1) True)

check :: (PrimMonad m) => V2 Int -> (MV2 (PrimState m) Bool, MV2 (PrimState m) Bool) -> [(Int, Edge)] -> m Int
check vs (fs, gs) = loop 0
--check vs idxs = runST (newVec >>= loop 0 idxs)
    where
        --n = V.length vs
{-
        newVec :: ST s (MV2 s Bool, MV2 s Bool)
        newVec = (,) <$> (VM.replicateM n $ VM.replicate n False) <*> (VM.replicateM n $ VM.replicate n True)
-}
        -- loop :: Int -> [(Int, Edge)] -> ST s Int
        loop acc ((i, e) : xs) -- (fs, gs)
            | (vs `at` (i, j)) > (vs `at` (i, k)) + w = return $ -1
            | (vs `at` (i, j)) == (vs `at` (i, k)) + w = readFlags >>= checkFlags
            | otherwise = loop acc xs -- (fs, gs)
            where
                j = to e 
                k = from e
                w = weight e
                readFlags = (,) <$> (readM fs (i, j)) <*> (readM gs (k, j))
                checkFlags (f, g)
                    | f = loop acc xs -- (fs, gs)
                    | g = writeM fs (i, j) True >> writeM gs (k, j) False >> loop (acc + w) xs --(fs, gs)
                    | otherwise = writeM fs (i, j) True >> loop acc xs --(fs, gs) 
        loop acc _ {-_-} = return $ acc `div` 2

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