# encoding: utf-8                                                                                            

class Graph
  INF = 0x3fffffff
  def initialize(v)
    @v = v
    @edges = []
    @g = []
    @v.times.each { |idx| @g << Hash.new}
    @dists = [INF] * @v
    @prevs = [-1] * @v
  end

  def add_edge(u, v, w)
    @g[u][v] = w
  end

  def dijkstra(s)
    @dists[s] = 0
    que = { }
    que[s] = 0


    while not que.empty?
      v, d = que.min_by { |key, val| val}
      que.delete_if { |key, val| key == v and val == d}
      @g[v].each do |to, dist|
        if @dists[to] > @dists[v] + dist
          @prevs[to] = v
          @dists[to] = @dists[v] + dist
          que[to] = @dists[to]
        end
      end
    end
  end

  def solve(s)
    dijkstra(s)
    @dists.each_with_index do |dist, idx|
      puts "#{idx} #{dist}"
    end
  end

end


def input
  n = gets.to_i
  graph = Graph.new(n)
  (1..n).each do |node|
    arr = gets.rstrip.split(/\s/).map(&:to_i)
    u, k, edges = arr[0], arr[1], arr[2..-1]
    k.times { |ik| graph.add_edge(u, edges[2 * ik], edges[2 * ik + 1])}
  end
  graph
end

g = input
g.solve(0)