import java.io.{BufferedOutputStream, BufferedReader, FileOutputStream, InputStreamReader, PrintWriter}
import java.lang

import scala.annotation.tailrec
import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer
import scala.reflect.ClassTag

object Main {
  val DEBUG = true

  lazy val debugOut: PrintWriter = {
    new PrintWriter(new BufferedOutputStream(new FileOutputStream("log.txt", true)))
  }

  def log(message: => Any): Unit = {
    if (DEBUG) {
      debugOut.println(message)
    }
  }

  def logf(message: => Any): Unit = {
    if (DEBUG) {
      debugOut.println(message)
      debugOut.flush()
    }
  }

  def debug(closure: => Unit): Unit = {
    if (DEBUG) {
      closure
    }
  }

  def get[T: ClassTag](implicit in: BufferedReader, converter: String => T): T = {
    converter(in.readLine)
  }

  def getArray[T: ClassTag](implicit in: BufferedReader, converter: String => T): Array[T] = {
    get[String].split("\\s+").map[T](converter)
  }

  implicit val idConverter: String => String = s => s
  implicit val intConverter: String => Int = s => Integer.parseInt(s)
  implicit val longConverter: String => Long = s => lang.Long.parseLong(s)

  def get[T1, T2](
                   implicit in: BufferedReader,
                   converter1: String => T1,
                   converter2: String => T2
                 ): (T1, T2) = {
    getArray[String] match {
      case Array(v1, v2) => (converter1(v1), converter2(v2))
    }
  }

  def get[T1, T2, T3](
                       implicit in: BufferedReader,
                       converter1: String => T1,
                       converter2: String => T2,
                       converter3: String => T3
                     ): (T1, T2, T3) = {
    getArray[String] match {
      case Array(v1, v2, v3) => (converter1(v1), converter2(v2), converter3(v3))
    }
  }

  def get[T1, T2, T3, T4](
                           implicit in: BufferedReader,
                           converter1: String => T1,
                           converter2: String => T2,
                           converter3: String => T3,
                           converter4: String => T4
                         ): (T1, T2, T3, T4) = {
    getArray[String] match {
      case Array(v1, v2, v3, v4) => (converter1(v1), converter2(v2), converter3(v3), converter4(v4))
    }
  }

  implicit class TimesInt(val n: Int) {
    def times(f: Int => Unit): Unit = {
      for (i <- 0 until n) {
        f(i)
      }
    }
  }

  def primes(n: Long): ArrayBuffer[Long] = {
    val buf = ArrayBuffer.empty[Long]
    val s = Math.sqrt(n).toInt

    var v = n
    for (i <- 2 to s) {
      if (v == 1 || v == 0) {
        return buf
      } else {
        while (v % i == 0) {
          buf.append(i)
          v /= i
        }
      }
    }
    if (v > s) {
      buf.append(v)
    }
    buf
  }

  def divisors(n: Int): ArrayBuffer[Int] = {
    val buf = ArrayBuffer.empty[Int]
    val s = Math.sqrt(n).toInt

    for (i <- 1 to s) {
      if (n % i == 0) {
        buf.append(i)
        if (i != n / i) {
          buf.append(n / i)
        }
      }
    }
    buf
  }

  @tailrec
  def gcd(a: Long, b: Long): Long = {
    val reminder = a % b
    if (reminder == 0) {
      b
    } else {
      gcd(b, reminder)
    }
  }

  @tailrec
  def gcd(a: Int, b: Int): Int = {
    val reminder = a % b
    if (reminder == 0) {
      b
    } else {
      gcd(b, reminder)
    }
  }

  def lcm(a: Long, b: Long): Long = {
    a / gcd(a, b) * b
  }

  def toBitArray(n: Int, width: Int): Array[Boolean] = {
    val buf = ArrayBuffer.fill(width)(false)

    @tailrec
    def inner(n: Int, i: Int): Array[Boolean] = {
      buf(i) = (n & 1) == 0
      if (i == 0) {
        buf.toArray
      } else {
        inner(n / 2, i - 1)
      }
    }

    inner(n, width - 1)
  }

  class ModInt[@specialized(Int) T <: Int](v: Long)(implicit val _m: ValueOf[T]) {
    val m: Long = _m.value
    var value: Long = v % m
    if (value < 0L) {
      value += m
    }

    @inline
    def getValue: Long = value

    override def toString: String = value.toString

    def +(other: ModInt[T]): ModInt[T] = new ModInt[T](value) += other

    def +=(other: ModInt[T]): this.type = {
      value += other.getValue
      if (value >= m) {
        value -= m
      }
      this
    }

    def -(other: ModInt[T]): ModInt[T] = new ModInt(value) -= other

    def -=(other: ModInt[T]): this.type = {
      value -= other.getValue
      if (value < 0) {
        value += m
      }
      this
    }

    def *(other: ModInt[T]): ModInt[T] = new ModInt(value) *= other

    def *=(other: ModInt[T]): this.type = {
      value = value * other.getValue % m
      this
    }

    def /(other: ModInt[T]): ModInt[T] = new ModInt(value) /= other

    def /=(other: ModInt[T]): this.type = {
      var a = other.getValue
      var b = m.toLong
      var u = 1L
      var v = 0L

      while (b > 0L) {
        val t = a / b;
        a -= t * b
        a = a ^ b
        b = a ^ b
        a = a ^ b

        u -= t * v
        u = u ^ v
        v = u ^ v
        u = u ^ v
      }

      value = value * u % m
      if (value < 0) {
        value += m
      }
      this
    }

    def modpow(p: Long): ModInt[T] = {
      @tailrec
      def inner(n: ModInt[T], p: Long, acc: ModInt[T]): ModInt[T] = {
        if (p == 0) {
          acc
        } else if ((p & 1) == 0) {
          inner(n *= n, p >> 1, acc)
        } else {
          inner(n *= n, p >> 1, acc *= n)
        }
      }

      inner(new ModInt[T](value), p, new ModInt[T](1))
    }

    override def equals(other: Any): Boolean = {
      other match {
        case other: ModInt[T] =>
          m == other.m && value == other.value
        case _ => false
      }
    }

    override def hashCode(): Int = {
      (m + value).intValue()
    }
  }

  def main(args: Array[String]): Unit = {
    implicit val in: BufferedReader = new BufferedReader(new InputStreamReader(System.in))
    val out = new PrintWriter(new BufferedOutputStream(System.out))

    log("=== start")
    val n = get[Int]
    val edges = Array.fill(n - 1) {
      get[Int, Int] match {
        case (a, b) => (a - 1, b - 1)
      }
    }
    val cs = getArray[Int].sorted(Ordering[Int].reverse)
    val csQueue = mutable.Queue.from(cs)

    debug {
      logf(">>>input")
      logf(n)
      edges.foreach {
        case (a, b) => logf(s"${a + 1} ${b + 1}")
      }
      logf(cs.mkString(" "))
    }

    val node2node = mutable.HashMap.empty[Int, mutable.Set[Int]].withDefault(_ => mutable.Set.empty[Int])
    for ((a, b) <- edges) {
      node2node(a) = node2node(a).addOne(b)
      node2node(b) = node2node(b).addOne(a)
    }

    val ds = Array.ofDim[Int](n)
    val queue = mutable.Queue.empty[Int]
    queue.enqueue(node2node.find {
      case (_, set) => set.size == 1
    }.get._1)

    while (queue.nonEmpty) {
      val nodeId = queue.dequeue()
      node2node.get(nodeId) match {
        case Some(nodes) =>
          val c = csQueue.dequeue()

          ds(nodeId) = c

          queue.enqueueAll(nodes)
          node2node.remove(nodeId)
        case None =>
      }
    }

    out.println(cs.sum - cs.head)
    out.println(ds.mkString(" "))

    debug {
      logf(">>>>result")
      logf(cs.sum - cs.head)
      logf(ds.mkString(" "))
    }

    out.flush()
    log("=== end")
    debug {
      debugOut.flush()
    }
  }
}

Measured memory_bytes: 63904