'use strict'
function main(input) {
  input = input.trim().split('\n')
  const N = Number(input.shift())
  const C = input.pop().split(' ')
    .map(v => Number(v)).sort((a, b) => b - a)
  input = input.map(v => v.split(' ').map(w => Number(w)))

  let countI = [].concat(...input).sort()
  let count = new Array(N).fill(0)
  countI.forEach(val => count[val-1] += 1)
  count = count
    .map((v, i) => ({num: i+1, count: v}))
    .sort((a, b) => b.count - a.count)
  let sc = count
    .map((v, i) => ({num: v.num, c: C[i]}))
    .sort((a, b) => a.num - b.num).map(arr => arr.c)

  let ans = 0
  input.forEach(arr => {
    ans += Math.min(sc[arr[0] - 1], sc[arr[1] - 1])
  })

  console.log(ans + '\n' + sc.join(' '))
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
