#include <bits/stdc++.h>
using namespace std;
int n;
int cost[200];
vector<int> con[200];
vector<int> ch[200];
int d0[200][200];
int f0[200][200];
int q0[200][200];
int d1[200][200];
int f1[200][200];
void build_tree(int cur, int p = -1) {
  for (int i = 0; i < con[cur].size(); i++)
    if (con[cur][i] != p) {
      ch[cur].push_back(con[cur][i]);
      build_tree(ch[cur].back(), cur);
    }
}
void print_tree() {
  for (int i = 0; i < n; i++) {
    cout << i << " ->";
    for (int j = 0; j < ch[i].size(); j++) cout << " " << ch[i][j];
    cout << endl;
  }
}
int calc_d1(int, int);
int calc_d0(int i, int l) {
  if (d0[i][l] == -1) {
    int& res = d0[i][l];
    int& f = f0[i][l];
    res = cost[0];
    for (int j = 0; j < ch[i].size(); j++) res += calc_d0(ch[i][j], 1);
    f = -1;
    if (l < n) {
      int cnt = cost[l];
      for (int j = 0; j < ch[i].size(); j++) cnt += calc_d0(ch[i][j], l + 1);
      if (cnt < res) {
        res = cnt;
        f = -2;
      }
    }
    for (int r = 1; r < l; r++) {
      for (int q = 0; q < ch[i].size(); q++) {
        int cnt = calc_d1(ch[i][q], r - 1) + cost[r];
        for (int j = 0; j < ch[i].size(); j++)
          if (j != q) cnt += calc_d0(ch[i][j], r + 1);
        if (cnt < res) {
          res = cnt;
          f = r;
          q0[i][l] = q;
        }
      }
    }
  }
  return d0[i][l];
}
int calc_d1(int i, int r) {
  if (d1[i][r] == -1) {
    int& res = d1[i][r];
    int& f = f1[i][r];
    if (r == 0) {
      res = cost[0];
      for (int j = 0; j < ch[i].size(); j++) res += calc_d0(ch[i][j], 1);
    } else {
      res = 2000000000;
      for (int q = 0; q < ch[i].size(); q++) {
        int cnt = calc_d1(ch[i][q], r - 1) + cost[r];
        for (int j = 0; j < ch[i].size(); j++)
          if (j != q) cnt += calc_d0(ch[i][j], r + 1);
        if (cnt < res) {
          res = cnt;
          f = q;
        }
      }
    }
  }
  return d1[i][r];
}
int cities[200];
int restore_d1(int, int);
void restore_d0(int i, int l, int top_city) {
  int f = f0[i][l];
  int q = q0[i][l];
  if (f == -1) {
    cities[i] = i;
    for (int j = 0; j < ch[i].size(); j++) restore_d0(ch[i][j], 1, i);
  } else if (f == -2) {
    cities[i] = top_city;
    for (int j = 0; j < ch[i].size(); j++)
      restore_d0(ch[i][j], l + 1, top_city);
  } else {
    cities[i] = restore_d1(ch[i][q], f - 1);
    for (int j = 0; j < ch[i].size(); j++)
      if (j != q) restore_d0(ch[i][j], f + 1, cities[i]);
  }
}
int restore_d1(int i, int r) {
  int q = -1;
  if (r == 0) {
    cities[i] = i;
  } else {
    q = f1[i][r];
    cities[i] = restore_d1(ch[i][q], r - 1);
  }
  for (int j = 0; j < ch[i].size(); j++)
    if (j != q) restore_d0(ch[i][j], r + 1, cities[i]);
  return cities[i];
}
int main() {
  cin >> n >> cost[0];
  for (int i = 1; i <= n - 1; i++) cin >> cost[i];
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    con[a].push_back(b);
    con[b].push_back(a);
  }
  build_tree(0);
  memset(d0, -1, sizeof(d0));
  memset(d1, -1, sizeof(d1));
  cout << calc_d0(0, n) << endl;
  restore_d0(0, n, -1);
  for (int i = 0; i < n; i++) cout << cities[i] + 1 << " ";
  cout << endl;
}
