import Data.Maybe
import Data.List
import qualified Data.IntSet as S
import qualified Data.ByteString.Char8 as B

data Edge = Edge { src :: Int, dst :: Int, cost :: Int } deriving Show
type Node = (Int, [Int])
type Index = Int

appendEdges :: [Node] -> Int -> [Edge] -> [Edge]
appendEdges l m edges = [edge | edge <- edges', src edge >= 0 && dst edge >= 0]
  where
    sortFunc (i, c) (j, c') = compare (c !! m) (c' !! m)
    l' = sortBy sortFunc l
    f (z, (i, c)) (j, c') =
      let cost = (c' !! m) - (c !! m)
      in (Edge i j cost : Edge j i cost : z, (j, c'))
    (edges', _) = foldl' f (edges, (-1, [0, 0])) l'


data State = State { s :: S.IntSet, total :: Int } deriving Show
mst' :: Index -> State -> Int -> [Edge] -> Int
mst' i state@(State s total) n edges
  | S.size s == n = total
  | S.notMember src s || S.notMember dst s =
      let s' = S.insert dst $ S.insert src s
          total' = total + cost
          state' = State s' total'
      in mst' i' state' n edges
  | otherwise = mst' i' state n edges
  where
    Edge src dst cost = edges !! i
    i' = i + 1


mst :: Int -> [Edge] -> Int
mst = mst' 0 init
  where
    init = State S.empty 0

solve :: [[Int]] -> Int
solve l = mst n edges
  where
    l' = zip [1..] l
    n = length l
    edges = sortOn cost $ appendEdges l' 1 $ appendEdges l' 0 []

readInt = fst . fromJust . B.readInt
main = B.getContents >>= print . solve . map (map readInt . B.words) . tail . B.lines
