n = gets.chomp.to_i
ab = []
cn = {}
cns = {}
n.times do |i|
  cn[i+1] = nil
  cns[i+1] = nil
end
(n-1).times do
  ab << gets.chomp.split.map(&:to_i)
  a, b = ab.last
  [a, b].each do |al|
    if !cn[al]
      cn[al] = 1
      cns[al] = ab.last
    elsif cn[al] == 1
      cn[al] = 2
    end
  end
end

c = gets.chomp.split.map(&:to_i).sort
puts c[0..(n-2)].inject(:+)

ans = []
n.times do |i|
  ans[i] = nil
end

n.times do |i|
  if cn[i+1] == 1
    ans[i] = c.shift
    ab.delete(cns[i+1])
  end
end

while ab != []
  n.times do |i|
    cn[i+1] = nil
    cns[i+1] = nil
  end
  ab.each do |abl|
    abl.each do |al|
      if !cn[al]
        cn[al] = 1
        cns[al] = abl
      elsif cn[al] == 1
        cn[al] = 2
      end
    end
  end
  n.times do |i|
    if cn[i+1] == 1
      ans[i] = c.shift
      ab.delete(cns[i+1])
    end
  end
end

n.times do |i|
  ans[i] = c.shift if !ans[i]
end

n.times do |i|
  print ans[i]
  print " " if i != n-1
end
print "\n"