n = STDIN.gets.to_i
matrix = Array.new(n) { Array.new(n) }
n.times do
	vertex, degree, *adjacent_info = STDIN.gets.split.map(&:to_i)
	degree.times do
		adjacency, weight = adjacent_info.shift(2)
		matrix[vertex][adjacency] = weight
	end
end

# ダイクストラ法
MAX_WEIGHT = 100_001
distances = Array.new(n)
visited   = Array.new(n, false)
parent    = Array.new(n)

distances[0] = 0
loop do
	vertex = matrix.each_index.
		select { |i| !visited[i] }.
		min_by { |i| distances[i] || MAX_WEIGHT }

	break if vertex.nil?
	visited[vertex] = true

	matrix.each_index do |i|
		next if visited[i] || matrix[vertex][i].nil?

		tmp_distance = distances[vertex] + matrix[vertex][i]
		if distances[i].nil? || tmp_distance < distances[i]
			distances[i] = tmp_distance
			parent[i] = vertex
		end
	end
end

matrix.each_index { |i| puts "#{i} #{distances[i]}" }