$n = gets.to_i
INF = 10000000
$d = Array.new($n){ Array.new }
$n.times do
  l = gets.split.map(&:to_i)
  (1..l[1]).each do |i|
    $d[l[0]] << l[2*i,2]
  end
end

def dijkstra(x)
  cost = Array.new($n, INF)
  cost[x] = 0
  visited = Array.new($n, false)

  while visited.include?(false)
    m = INF

    # visited???????????????????????????????????????m???
    $n.times do |i|
      if !visited[i] && m > cost[i] then
        m = cost[i]
      end
    end

    # INF???????????£????????????
    break if m == INF

    # ???????????§????????????????¨????
    # ????????????m????????£??????visited??¨???????¢????
    $n.times do |j|
      if m == cost[j]
        visited[j] = true
        $d[j].each do |r|
          u, w = r
          cost[u] = [cost[u], cost[j] + w].min
        end
      end
    end
  end
  cost
end

result = dijkstra(0)
result.each_index{ |i| puts "#{i} #{result[i]}" }