"use strict";
function Main(input) {
  const args = input.split('\n');
  const N = parseInt(args.shift());
  const ns = Array(N).fill(0);
  const cs = args[N - 1].split(' ').map(m => parseInt(m)).sort((a, b) => a - b);
  const ms = [];
  const abs = [];
  for(let i = 0; i < args.length - 2; i++) {
    const ab = args[i].split(' ').map(m => parseInt(m) - 1);
    abs.push(ab);
    ns[ab[0]]++;
    ns[ab[1]]++;
  }
  let ds = [];
  ns.map((m, i) => {
    return {
      idx: i,
      count: m
    }
  })
  .sort((a, b) => a.count - b.count)
  .forEach((v, i) => ds[v.idx] = cs[i]);
  for(let ab of abs) {
    const a = ab.shift();
    const b = ab.shift();
    ms.push(ds[a] < ds[b] ? ds[a] : ds[b]);
  }
  const M = ms.reduce((p ,c) => p += c);
  console.log(M);
  console.log(ds.join(' '));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));
