{-# LANGUAGE FlexibleContexts #-}

module Main where

-- import Debug.Trace
import Data.List
import qualified Data.Set as Set
import qualified Data.Sequence as Seq
import qualified Data.ByteString.Char8 as B
import Data.Int
import Data.Char
import Data.Array
-- import Data.Array.IO
import Data.Maybe
import qualified Data.Map as M
-- import Control.Monad.ST
-- import Data.STRef
import Data.Ord
import Data.Functor
import Control.Applicative
import Control.Monad
import Text.Printf

data Edge = Edge Int Int Int deriving (Eq, Show) -- Edge <left> <weight> <right>
instance Ord Edge where
    compare (Edge la wa ra) (Edge lb wb rb) = case (la,lb,ra,rb,wa,wb) of
      _ | wa > wb -> GT  
        | wa < wb -> LT 
        | la > lb -> GT 
        | la < lb -> LT 
        | ra > rb -> GT 
        | ra < rb -> LT
        | otherwise -> EQ


solve :: Int -> [[Int]] -> Int
solve n lst = sumWeight edgesOfMST where
    sumWeight = Set.foldl' (\a (Edge _ w _) -> a + w) 0
    edgesOfMST = iter Set.empty Set.empty (Set.singleton (Edge 0 0 1)) where
        iter vertices edges adjacents
            | Set.null adjacents = edges
--            | otherwise = trace (printf "Tr0\tvtx :%s\n\tvtx':%s\n\teds :%s\n\teds':%s\n\tads :%s\n\tads':%s" (show vertices) (show vertices') (show edges) (show edges') (show adjacents) (show adjacents')) $
            | otherwise = iter vertices' edges' adjacents' where
                vertices'  = Set.insert r vertices
                edges'     = Set.insert e edges
                adjacents' = updateAdjacents s
                (e@(Edge _ _ r), s) = Set.deleteFindMin adjacents
                updateAdjacents s = iter s n where
                    iter s 0 = s
                    iter s i = iter (update s) (i-1) where 
                        update s
                            | w < 0 = s
                            | Set.member i vertices = s
                            | otherwise = iter (Set.size s -1) where
                                iter (-1) = Set.insert e s
                                iter j = case Set.elemAt j s of
                                    (Edge ls ws rs)
                                        | i == rs   -> if ws > w then Set.insert e (Set.deleteAt j s) else s
                                        | otherwise -> iter (j-1)
                                w = adjacentsMatrix!(i, r)
                                e = Edge r w i

    adjacentsMatrix = (listArray ((1,1),(n,n)) (concat lst)) // [((x,x),-1)| x<-[1..n]]

readIntLn:: IO Int
readIntLn = (fst . fromJust . B.readInt) <$> B.getLine

readIntList:: IO [Int]
readIntList = map (fst . fromJust . B.readInt) . B.words <$> B.getLine

main :: IO() 
main = do
    n  <- readIntLn
    l <- replicateM n readIntList
    print $ solve n l

