import Control.Monad
import Control.Monad.ST
import Data.STRef
import qualified Data.ByteString.Char8 as C
import Data.Ord
import Data.Vector.Unboxed
import qualified Data.Vector.Unboxed.Mutable as UM
import Data.Vector.Algorithms.Intro
import Prelude hiding (head, tail, zipWith, (++), enumFromTo)

main = C.interact $ put . sol . get

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

put = C.pack . show

sol v = kruskal n (ex++ey)
  where
  n = head v
  u = tail v
  vs = generate n id
  ex = es x $ modify (sortBy (comparing x)) vs
  ey = es y $ modify (sortBy (comparing y)) vs
  x i = u!(2*i)
  y i = u!(2*i+1)
  es f is = zipWith (\i j -> (f i-f j,i,j)) (tail is) is

data UnionFind s = UnionFind {ids :: UM.STVector s Int, szs :: UM.STVector s Int}

newUF n = liftM2 UnionFind (unsafeThaw $ enumFromTo 0 (n-1)) (UM.replicate n 1)

findUF uf p q = liftM2 (==) (rootUF uf p) (rootUF uf q)

rootUF uf i = do
  p <- UM.unsafeRead (ids uf) i
  if p==i
    then return i
    else do
      gp <- UM.unsafeRead (ids uf) p
      if gp==p
        then return p
        else do
          UM.unsafeWrite (ids uf) i gp
          rootUF uf i

uniteUF uf p q = do
  i <- rootUF uf p
  j <- rootUF uf q
  si <- UM.unsafeRead (szs uf) i
  sj <- UM.unsafeRead (szs uf) j
  if si<sj
    then do
      UM.unsafeWrite (ids uf) i j
      UM.unsafeWrite (szs uf) j (si+sj)
    else do
      UM.unsafeWrite (ids uf) j i
      UM.unsafeWrite (szs uf) i (si+sj)

kruskal n = go n . modify sort

go n es = runST $ do
  uf <- newUF n
  a <- newSTRef 0
  foldM'_ upd (uf,a) es
  readSTRef a

upd (uf,a) (c,i,j) = do
  b <- findUF uf i j
  unless b $ do
    uniteUF uf i j
    modifySTRef' a (+c)
  return (uf,a)