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

data Edge = Edge { src :: Int, dst :: Int, cost :: Int } deriving Show
type Node = (Int, [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'


step (s, total) (Edge src dst cost)
  | S.notMember src s || S.notMember dst s = (S.insert dst (S.insert src s), total + cost)
  | otherwise = (s, total)

mst :: [Edge] -> Int
mst edges = snd $ foldl' step (S.empty, 0) edges

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

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