object Main extends App {
  val in = scala.io.Source.stdin.getLines.toSeq
  val ls = in.map(_.split(' ').map(_.toInt))
  val N = ls.head(0)
  val lstail = ls.tail
  val a = lstail.init
  val c = lstail.last
  val cSorted = c.sorted
  val cnt = (0 to N).map(_ => 0).toArray
  a.foreach{ e =>
    cnt(e(0)) += 1
    cnt(e(1)) += 1
  }
  val cnti = cnt.zipWithIndex.tail //remove 0
  val cntiSorted = cnti.sortBy(_._1)
  val ass = (0 to N).map(_ => -1).toArray  
  cntiSorted.indices.foreach{ i =>
    ass(cntiSorted(i)._2) = cSorted(i)
  }
  val ret = a.indices.foldLeft(0L){ (acc,i) =>
    val ai = a(i)
    val e0 = ass(ai(0))
    val e1 = ass(ai(1))
    acc + Math.min(e0, e1)
  }
  println(ret)
  println(ass.tail.mkString(" "))
}
