# util functions

# debug
$debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if $debugFlag

def pd(str)
  p str if $debugFlag
end

# input
inputs = []
lc = 0
nn = 0
scores = []
edge = []
while l = $stdin.gets do
  if lc == 0
    nn = l.chomp.to_i
    initedgev = [0]*nn
    nn.times do 
      edge << initedgev.clone
    end
  elsif lc < nn
    tmp_edge = l.chomp.split(" ").map(&:to_i)
    tmp_a = tmp_edge[0] - 1
    tmp_b = tmp_edge[1] - 1
    edge[tmp_a][tmp_b] = 1
    edge[tmp_b][tmp_a] = 1
  else # lc == nn
    scores = l.chomp.split(" ").map(&:to_i)
  end
  lc += 1
end
scores = scores.sort.reverse

pd nn
edge.each do |x_i|
  pd x_i
end
pd scores
pd ans_val = scores[1..-1].inject(:+)

# input check
if $debugFlag
  p "--- INPUT (begin) ---"
  inputs.each do |l_i|
    p l_i
  end
  p "--- INPUT (end) ---"
  print "\n"
end

# body
if $debugFlag
end

ans = []
queue = [0]
while queue != []
  print "queue: " if $debugFlag
  pd queue
  node = queue.shift
  ans[node] = scores.shift
  break if node == nn - 1
  for i in node+1..nn-1
    queue.push(i) if edge[node][i] == 1
  end
end
pd ans

str = ""
ans.each do |a_i|
  str += "#{a_i} "
end

puts ans_val
puts str.chomp
