from scipy.sparse import*

n,*t=list(map(int,open(0).read().split()))

c=sorted(t[-n:])

i=n

for j in csgraph.depth_first_order(csr_matrix((t[:n-1],(t[:-n:2],t[1:-n:2])),[n+1]*2),1,0,0):i-=1;t[j-1]=c[i]

print((sum(c[:-1]),*t[:n]))
from scipy.sparse import*

n,*t=list(map(int,open(0).read().split()))

c=sorted(t[-n:])

f=c[:]

for i in csgraph.depth_first_order(csr_matrix((f[1:],(t[:-n:2],t[1:-n:2])),[n+1]*2),1,0,0):n-=1;f[i-1]=c[n]

print((sum(c[:-1]),*f))
from scipy.sparse import *

n, *t = list(map(int, open(0).read().split()))
c = sorted(t[-n:])
i = n
for j in csgraph.depth_first_order(
    csr_matrix((t[: n - 1], (t[:-n:2], t[1:-n:2])), [n + 1] * 2), 1, 0, 0
):
    i -= 1
    t[j - 1] = c[i]
print((sum(c[:-1]), *t[:n]))

from scipy.sparse import *

n, *t = list(map(int, open(0).read().split()))
c = sorted(t[-n:])
f = c[:]
for i in csgraph.depth_first_order(
    csr_matrix((f[1:], (t[:-n:2], t[1:-n:2])), [n + 1] * 2), 1, 0, 0
):
    n -= 1
    f[i - 1] = c[n]
print((sum(c[:-1]), *f))

-i = n -for j in csgraph.depth_first_order( -    csr_matrix((t[: n - 1], (t[:-n:2], t[1:-n:2])), [n + 1] * 2), 1, 0, 0 +f = c[:] +for i in csgraph.depth_first_order( +    csr_matrix((f[1:], (t[:-n:2], t[1:-n:2])), [n + 1] * 2), 1, 0, 0 -    i -= 1 -    t[j - 1] = c[i] -print((sum(c[:-1]), *t[:n])) +    n -= 1 +    f[i - 1] = c[n] +print((sum(c[:-1]), *f))