{-# 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 Vertex = Vt Int Int deriving (Eq, Show) -- Vt <ID> <Distance>
instance Ord Vertex where
    compare (Vt ia da) (Vt ib db) =
        case (ia ,da, ib, db) of
         _  | ia == ib -> EQ 
            | ia >  ib -> GT 
            | ia <  ib -> LT

solve :: Int -> [[Int]] -> [Vertex]
solve n lst = iter Set.empty initialQ where
    iter r q 
        | Set.null q = Set.toAscList r
        | otherwise = iter r' q' where
            r' = Set.insert v r
            q' = iter restQ (adjacencyList!i) where
                    iter q [] = q
                    iter q ((j, d):rest) = case Set.lookupGE (Vt j 0) q of
                        Just (Vt k c')
                            | j == k -> iter (Set.insert (Vt j (min (c+d) c')) q) rest
                            | otherwise -> iter q rest
                        Nothing -> iter q rest
            v@(Vt i c) = Set.foldl minCost (Vt n maxBound) q where
                minCost a@(Vt ia ca) b@(Vt ib cb) = if ca < cb then a else b
            restQ = Set.delete v q
            
    initialQ = Set.fromList $ [Vt 0 0] ++ [Vt x maxBound | x <- [1..n-1]]

    adjacencyList = array (0, n-1) (setupAL [] lst)
    setupAL al [] =  al
    setupAL al ((u:_:vcs):lines) = setupAL ((iter [] vcs):al) lines where
        iter av [] = (u, av)
        iter av (v:c:rest) = iter ((v,c):av) rest

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

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

print' :: Vertex -> IO ()
print' (Vt x y) = putStrLn $ show x ++ " " ++ show y

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

