N=gets.to_i
tmp = $<.read.split.map(&:to_i)
abs=tmp[0..(N-1)*2-1].each_slice(2)
cs=tmp[(N-1)*2..-1].sort

tree = Array.new(N+1) { [] }

min = 10000
abs.each do |a,b|
  a,b = a<b ? [a,b] : [b,a]
  min = a if a < min
  tree[a] << b
end

q = tree[min]
ret = Array.new(N+1) { 0 }
ret[1] = cs.pop
while !q.empty?
  e=q.shift
  if ret[e] == 0
    ret[e]=cs.pop
    q+=tree[e]
  end
end

sum = cs[0..-2].inject(&:+)
puts sum
puts ret[1..-1].join(' ')