N=gets.to_i
tmp = $<.read.split.map(&:to_i)
abs=tmp[0..(N-1)*2-1].each_slice(2)
cs=[0] + tmp[(N-1)*2..-1].sort_by{|n|-n}

ret = abs.reduce(0) {|n,ab| n + [cs[ab[0]], cs[ab[1]]].min }

puts ret
puts cs[1..-1].join(' ')

