class PriorityQueue
  def initialize(array = [])
    @data = []
    array.each{|a| push(a)}
  end

  def push(element)
    @data.push(element)
    bottom_up
  end

  def pop
    if size == 0
      return nil
    elsif size == 1
      return @data.pop
    else
      min = @data[0]
      @data[0] = @data.pop
      top_down
      return min
    end
  end

  private

  def swap(i, j)
    @data[i], @data[j] = @data[j], @data[i]
  end

  def size
    @data.size
  end

  def parent_idx(target_idx)
    (target_idx - (target_idx.even? ? 2 : 1)) / 2
  end

  def bottom_up
    target_idx = size - 1
    return if target_idx == 0
    parent_idx = parent_idx(target_idx)
    while (@data[parent_idx][1] > @data[target_idx][1])
      swap(parent_idx, target_idx)
      target_idx = parent_idx
      break if target_idx == 0
      parent_idx = parent_idx(target_idx)
    end
  end

  def top_down
    target_idx = 0

    # child がある場合
    while (has_child?(target_idx))

      a = left_child_idx(target_idx)
      b = right_child_idx(target_idx)

      if @data[b].nil?
        c = a
      else
        c = @data[a][1] <= @data[b][1] ? a : b
      end

      if @data[target_idx][1] > @data[c][1]
        swap(target_idx, c)
        target_idx = c
      else
        return
      end
    end
  end

  # @param Integer
  # @return Integer
  def left_child_idx(idx)
    (idx * 2) + 1
  end

  # @param Integer
  # @return Integer
  def right_child_idx(idx)
    (idx * 2) + 2
  end

  # @param Integer
  # @return Boolent
  def has_child?(idx)
    ((idx * 2) + 1) < @data.size
  end
end

def sssp ls, n
  colors = Array.new(n){1} # 1:white, 2:gray, 3:black
  ds = Array.new(n){Float::INFINITY}
  ds[0] = 0
  # pq = PQueue.new([[0, 0]]){|a, b| a[1] < b[1]}
  pq = PriorityQueue.new([[0, 0]])
  cnt = 0

#  while true do
  while cnt < n
#    break if pq.length == 0
    i, cost = pq.pop
    next if colors[i] == 3
    colors[i] = 3
    cnt += 1

    k, *paths = ls[i]
    k.times do |kk|
      c_i = paths[kk * 2]
      if colors[c_i] != 3
        c  = paths[kk * 2 + 1]
        new_cost = c + cost
        if new_cost < ds[c_i]
          ds[c_i] = new_cost
          pq.push([c_i, new_cost])
        end
        colors[c_i] = 2
      end
    end
  end

  ds
end

n = gets.chomp.to_i
ls = Array.new(n)
n.times do |nn|
  _, i, *paths = gets.split(' ').map(&:to_i)
  ls[nn] = ([i] + paths)
end
costs = sssp(ls, n)
costs.each_with_index do |cost, i|
  puts "#{i} #{cost}"
end
