{-# LANGUAGE BangPatterns #-}

import           Control.Applicative
import           Control.Monad
import qualified Data.ByteString.Char8 as B

import           Data.Array.IArray
import           Data.Array.IO
import           Data.Array.MArray
import           Data.Function         (on)
import           Data.List

readi :: B.ByteString -> Int
readi b | Just (n, _) <- B.readInt b = n

dijk :: Array Int [(Int, Int)]
     -> IOUArray Int Bool
     -> IOUArray Int Int
     -> IO ()
dijk b c d = go
  where
    go :: IO ()
    go = do
        as <- filterM (readArray c . fst) =<< getAssocs d
        unless (null as) $ do
            let (i, _) = minimumBy (compare `on` snd) as
            writeArray c i False -- confirmed
            bs <- filterM (readArray c . fst) (b ! i)
            forM_ bs $ \(v, w) -> do
                di <- readArray d i
                dv <- readArray d v
                when (di + w < dv) $ writeArray d v (di + w)
            go

main :: IO ()
main = do
    let f []       = Nothing
        f (i:j:ks) = Just ((i, j), ks)

    n <- readLn
    xss <-
        replicateM n $ do
            (i:_:xs) <- fmap readi . B.words <$> B.getLine
            return (i, unfoldr f xs)

    let b = array (0, n-1) xss      :: Array Int [(Int, Int)]
    c <- newArray (0, n-1) True     :: IO (IOUArray Int Bool)
    d <- newArray (0, n-1) maxBound :: IO (IOUArray Int Int)
    writeArray d 0 0

    dijk b c d

    forM_ [0 .. n-1] $ \i -> do
        v <- readArray d i
        putStr (show i ++ " ")
        print v

