"use strict";

// read lines from stdin
const input = require("fs")
  .readFileSync("/dev/stdin", "utf8")
  .split("\n");

const N = parseInt(input[0], 10);
const nodes = [];
const D = input[N].split(" ").map((v) => parseInt(v, 10)).sort((a, b) => b - a);
const edges = [];

for (let i = 1; i < N; i++) {
  const edge = input[i].split(" ").map((v) => parseInt(v, 10));
  edges[i] = edge;

  if (!nodes[edge[0]]) {
    nodes[edge[0]] = { index: edge[0], count: 0 };
  }
  if (!nodes[edge[1]]) {
    nodes[edge[1]] = { index: edge[1], count: 0 };
  }

  nodes[edge[0]].count++;
  nodes[edge[1]].count++;
}

for (let i = 1; i < nodes.length; i++) {
  let max = { index: -1, count: -1 };
  let maxIndex = -1;

  for (let j = i; j < nodes.length; j++) {
    if (nodes[j].count > max.count) {
      max = nodes[j];
      maxIndex = j;
    }
  }

  let tmp = nodes[i];
  nodes[i] = nodes[maxIndex];
  nodes[maxIndex] = tmp;
}

let ansTree = [];
let ans = 0;

for (let i = 0; i < D.length; i++) {
  ansTree[nodes[i + 1].index - 1] = D[i];
}

for (let i = 1; i < N; i++) {
  const score = Math.min(ansTree[edges[i][0] - 1], ansTree[edges[i][1] - 1]);
  ans += score;
}

console.log(ans);
console.log(ansTree.join(" "));
