#include <bits/stdc++.h>
using namespace std;
int n, en, nw, id[185], w[185], in[185][185], pin[185][185], ax[185][185],
    f[185][185][2], head[185];
struct edge {
  int v, nxt, p[185][2];
} e[185 * 2];
void dfs(int, int);
void find(int, int, int, int);
void adde(int, int);
int main() {
  int i, u, v, ps = 0;
  scanf("%d %d", &n, &nw);
  for (i = 1; i < n; ++i) scanf("%d", &w[i]);
  for (i = 1; i < n; ++i) {
    scanf("%d %d", &u, &v);
    adde(u, v);
    adde(v, u);
  }
  memset(in, 0x3f, sizeof(in));
  dfs(1, 0);
  for (i = 0; i < n; ++i)
    if (f[1][ps][0] > f[1][i][0]) ps = i;
  find(1, 0, ps, 0);
  printf("%d\n", f[1][ps][0]);
  for (i = 1; i <= n; ++i) printf("%d ", id[i]);
  return 0;
}
void dfs(int u, int fa) {
  int i, d, v, ww;
  for (i = head[u]; i; i = e[i].nxt)
    if ((v = e[i].v) != fa) {
      dfs(v, u);
      f[u][0][0] += (ww = min(f[v][1][1], f[v][0][0]));
      if (f[v][1][1] == ww)
        e[i].p[0][0] = 3;
      else if (f[v][0][0] == ww)
        e[i].p[0][0] = 0;
      for (d = 1; d < n; ++d) {
        ww = min(f[v][d + 1][1], min(f[v][d][0], f[v][d - 1][0]));
        f[u][d][0] += ww;
        f[u][d][1] += ww;
        if (ww == f[v][d + 1][1])
          e[i].p[d][0] = e[i].p[d][1] = (d + 1) * 2 + 1;
        else if (ww == f[v][d][0])
          e[i].p[d][0] = e[i].p[d][1] = d * 2;
        else
          e[i].p[d][0] = e[i].p[d][1] = (d - 1) * 2;
        if (in[u][d] > f[v][d - 1][0] - ww) {
          in[u][d] = f[v][d - 1][0] - ww;
          pin[u][d] = i;
        }
      }
    }
  f[u][0][0] += nw;
  for (d = 1; d < n; ++d) {
    f[u][d][0] += in[u][d] + w[d];
    f[u][d][1] += w[d];
    e[pin[u][d]].p[d][0] = 2 * (d - 1);
  }
}
void find(int u, int fa, int d, int fl) {
  int i, v, ep;
  if (!fl && !d)
    id[u] = u;
  else if (fl)
    id[u] = id[fa];
  for (i = head[u]; i; i = e[i].nxt)
    if ((v = e[i].v) != fa)
      if (!((ep = e[i].p[d][fl]) & 1)) {
        find(v, u, ep >> 1, ep & 1);
        if (!fl && d == (ep >> 1) + 1) id[u] = id[v];
      }
  for (i = head[u]; i; i = e[i].nxt)
    if ((v = e[i].v) != fa)
      if ((ep = e[i].p[d][fl]) & 1) find(v, u, ep >> 1, ep & 1);
}
void adde(int u, int v) {
  e[++en].v = v;
  e[en].nxt = head[u];
  head[u] = en;
}
