import Control.Monad
import Control.Monad.ST
import qualified Data.ByteString.Char8 as C
import Data.Vector.Unboxed ((!), drop, modify, unsafeFreeze, unsafeThaw)
import qualified Data.Vector.Unboxed as U
import Data.Vector.Unboxed.Mutable (unsafeRead, unsafeWrite)
 
main = C.interact $ put . sol . get

get = U.unfoldr (C.readInt . C.dropWhile (<'0'))

put = C.pack . show

sol v = case n of
  1 -> 0
  2 -> a!1
  _ -> if a==b then U.sum (U.filter (< inf) c) `div` 2 else -1
  where
  n = v!0
  a = U.drop 1 v
  b = modify (f n) a
  c = modify (g n) a

f n v = do
  let
    putw i j = unsafeWrite v (i*n+j)
    getw i j = unsafeRead v (i*n+j)
  forM_ [0..n-1] $ \k ->
    forM_ [0..n-1] $ \i ->
      forM_ [0..n-1] $ \j -> do
        a <- getw i k
        b <- getw k j
        p <- getw i j
        putw i j (min p (a+b))

g n v = do
  let
    putw i j = unsafeWrite v (i*n+j)
    getw i j = unsafeRead v (i*n+j)
  forM_ [0..n-2] $ \i -> do
    forM_ [i+1..n-1] $ \j -> do
      d <- getw i j
      forM_ [0..n-1] $ \k -> when (k/=i && k/=j) $ do
        d0 <- getw i k
        d1 <- getw k j
        when (d0+d1<=d) $ putw i j inf >> putw j i inf

inf = maxBound `div` 4 :: Int