def shortest_path
  cost = Array.new(@n-1, Float::INFINITY).unshift(0)
  node = Marshal.load(Marshal.dump(cost))

  @n.times do
    now = node.index(node.compact.min)
    @graph[now].each_with_index do |x, i|
      unless x == nil
        alt = cost[now] + x
        if cost[i] > alt
          cost[i] = alt
          node[i] = alt
        end
      end
    end
    node[now] = nil
  end
  
  return cost
end


@n = gets.to_i
@graph = Array.new(@n).map{Array.new(@n,nil)}

@n.times do |i|
  input = gets.split(" ").map{|x| x.to_i}
  u = input.shift
  k = input.shift
  k.times do
    @graph[u][input.shift] = input.shift
  end
end

shortest_path.each_with_index do |x, i|
  printf "%d %d\n",i ,x
end

