require 'set'

N = gets.chomp.to_i
A = Array.new(N){Set.new}
h = Array.new(N){Array.new(2,0)}
i = 0
while i < N
  h[i][0] = i
  i += 1
end

str = gets.split
a,b = str[0].to_i-1, str[1].to_i-1
A[a].add(b)
A[b].add(a)
h[a][1] += 1
h[b][1] += 1

i = N-2
while i > 0
  str = gets.split
  a,b = str[0].to_i-1, str[1].to_i-1
  A[a].add(b)
  A[b].add(a)
  h[a][1] += 1
  h[b][1] += 1
  i -= 1
end
h.sort! {|a,b| a[1] <=> b[1]}
g = Array.new
i = 1
while h[i][1] == 1
  g.push(h[i-1][0])
  i += 1
end

str = gets.split
i = 0
c = Array.new(N)
while i < N
  c[i] = str[i].to_i
  i += 1
end

c.sort!
sum = c.inject(:+)
sum -= c[N-1]
x = 0
d = Array.new

t = 0
s = 0
while x < N
  t = g.pop
  p t
  A[t].each do |val|
    s = val
  end
  A[t].delete(s)
  A[s].delete(t)
  d.push(t)
  x += 1
  while A[s].size == 1
    t = s
    A[t].each do |val|
      s = val
    end
    d.push(t)
    A[s].delete(t)
    A[t].delete(s)
    x += 1
    if A[s].size == 0
      d.push(s)
      x += 1
    end
  end
  p d
end
e = Array.new(N)
for i in 0...N
  e[d[i]] = c[i]
end

puts sum
print e[0]
i = 1
while i < N
  print " "
  print e[i]
  i += 1
end
puts