import Control.Monad
import Control.Applicative ((<$>))
import Data.Vector.Unboxed ((//), generate, minIndex, (!))
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.List as L
import Debug.Trace (trace)


type AdjM = V.Vector (VU.Vector Int)
type Costs = VU.Vector Int
type Verified = VU.Vector Bool


main :: IO ()
main = do
    n    <- readLn :: IO Int
    adjm <- V.replicateM n $ adj n . toCs [] . map read . drop 2 . words <$> getLine :: IO AdjM
    let vs = VU.replicate n False                :: Verified
        ws = VU.cons 0 (VU.replicate (n - 1) (n * 100001)) :: Costs
        cs = snd $ dijkstra n adjm (vs, ws)
    VU.forM_ (generate n id) $ \i -> do
        putStrLn $ show i ++ " " ++ show (cs ! i)
  where
    adj n cs = (VU.replicate n (n * 100001)) // cs
    toCs accum []         = accum
    toCs accum (a:b:rest) = toCs ((a, b) : accum) rest


dijkstra :: Int -> AdjM -> (Verified, Costs) -> (Verified, Costs)
dijkstra n adjm (vs, cs)
    | VU.all id vs = (vs, cs)
    | otherwise    = dijkstra n adjm (vs', cs')
  where
    vs' = vs // [(mi, True)]
    mi  = (\(i,_,_) -> i) . VU.foldl' f (-1, False, n * 100001) $ VU.zip3 (generate n id) vs cs
      where
        f (ai, av, ac) (i, v, c)
            | v == False && c < ac = (i, v, c)
            | otherwise            = (ai, av, ac)

    cs' = cs // updatelist
    updatelist = VU.foldl' g [] $ VU.zip3 (generate n id) cs (adjm V.! mi)
    mc  = cs ! mi
    g accum (i, a, b)
        | a > mc + b = (i, mc + b) : accum
        | otherwise  = accum

