import qualified Data.Map.Strict as M

main = do
  n <- readLn
  as <- concat . map (dropWhile (/= 0) . map read . words) . lines <$> getContents
  let es = zip [(i,j) | i<-[0..n-1], j<-[i..n-1]] as
  let ma = M.fromList es
  let mb = warshallFloyd n es
  putStrLn $ maybe "-1" show (rrn n ma mb)

rrn n ma mb
  | any (uncurry (>)) dab = Nothing
  | otherwise = Just $ (dmax -) $ sum [wuv | u<-[0..n-1], v<-[u+1..n-1], w<-[0..n-1],
                                             u/=w, v/=w,
                                             let wuv = mb M.! (u,v), 
                                             wuv == mb M.! (min u w, max u w) + mb M.! (min v w, max v w)]
  where
    dmax = sum (M.elems mb)
    dab = zip (M.elems ma) (M.elems mb)

type Vertex = Int
type Weight = Int
type Edge = ((Vertex, Vertex), Weight)

data Flag = F | T | M deriving Eq
type Memo = M.Map (Vertex, Vertex) Weight

-- 0-indexed vertex
warshallFloyd :: Int -> [Edge] -> Memo
warshallFloyd n es = foldl shorten m0 kij
  where
    m0 = M.fromList es
    kij = [(k, i, j) | k <- [0 .. pred n], i <- [0 .. pred n], j <- [0 .. pred n], i<k, k<j]

shorten :: Memo -> (Vertex, Vertex, Vertex) -> Memo
shorten m (k, i, j) = M.insertWith min (i,j) (connect m k i j) m

connect :: Memo -> Vertex -> Vertex -> Vertex -> Weight
connect m k i j = w1 + w2
  where
    w1 = m M.! (i, k)
    w2 = m M.! (k, j)
