module MakeBinaryHeap (M : sig type t val compare : t -> t -> int end) = struct
  type t = { node : M.t array; mutable size : int }

  let make n (init : M.t) = { node = Array.make n init; size = 0 }

  let empty_p t = if t.size = 0 then true else false

  let pop t =
    let left i = 2*i in
    let right i = 2*i + 1 in
    let rec max_heapify i =
      let l = left i in
      let r = right i in
      let m = if l <= t.size && M.compare t.node.(l) t.node.(i) > 0 then l else i in
      let m = if r <= t.size && M.compare t.node.(r) t.node.(m) > 0 then r else m in
      if m <> i then begin
        let tmp = t.node.(i) in t.node.(i) <- t.node.(m); t.node.(m) <- tmp;
        max_heapify m
      end
    in
    let ret = t.node.(1) in
    t.node.(1) <- t.node.(t.size);
    t.size <- t.size - 1;
    max_heapify 1;
    ret

  let push x t =
    t.size <- t.size + 1;
    t.node.(t.size) <- x;
    let parent i = int_of_float (floor (float_of_int i) /. 2.) in
    let rec doit i =
      if i > 1 && M.compare t.node.(parent i) t.node.(i) < 0 then begin
        let tmp = t.node.(i) in t.node.(i) <- t.node.(parent i); t.node.(parent i) <- tmp;
        doit (parent i)
      end
    in
    doit t.size
end

module H = MakeBinaryHeap(struct type t = (int * int) let compare x y = fst x - fst y end)

let split str delim =
  let rec doit s acc =
    match
      try Some (String.rindex s delim) with _ -> None
    with
    | None -> s :: acc
    | Some i ->
        let s1 = String.sub s 0 i in
        let s2 = String.sub s (i + 1) (String.length s - String.length s1 - 1) in
        doit s1 (s2 :: acc)
  in
  doit str []

let dijkstra g n =
  let h = H.make 100000 (0, 0) in
  let d = Array.make n max_int in
  let b = Array.make n false in
  d.(0) <- 0;
  b.(0) <- true;
  H.push (0, 0) h;
  let rec duduwa u = function
    | [] -> ()
    | (v, _) :: tl when b.(v) = true -> duduwa u tl
    | (v, c) :: tl when d.(v) <= d.(u) + c -> duduwa u tl
    | (v, c) :: tl -> begin
        d.(v) <- d.(u) + c;
        H.push ((-d.(v)), v) h;
        duduwa u tl
      end
  and doit () =
    if not (H.empty_p h) then begin
      let (x, u) = H.pop h in
      b.(u) <- true;
      if d.(u) >= (-x) then duduwa u g.(u);
      doit ()
    end
  in
  doit ();
  d

let () =
  let n = read_int () in
  let g = Array.make n [] in
  let rec read i =
    if i < n then begin
      match List.map int_of_string (split (read_line ()) ' ') with
      | u :: _ :: l -> begin
          let rec make_pair acc = function
            | [] -> acc
            | f :: t :: tl -> make_pair ((f, t) :: acc) tl
            | _ -> exit 1
          in
          g.(u) <- make_pair [] l;
          read (i + 1)
        end
      | _ -> exit 1
    end
  in
  read 0;
  let d = dijkstra g n in
  Array.iteri (fun i e -> Printf.printf "%d %d\n" i e) d