#include <bits/stdc++.h>
using namespace std;
const int N = 200;
int i, j, k, l, m, n, o, tot, p, K, f[N][N], g[N][N], d[N], e[3 * N], e1[3 * N],
    nex[3 * N], sta[N], vist[N], s1[N], n1[N * 3], best[N], id[N];
int cen[N], dist[N], len[N][N];
void add(int u, int v) {
  nex[++l] = sta[u];
  sta[u] = l;
  e[l] = v;
}
void Init() {
  scanf("%d%d", &n, &K);
  l = 1;
  for (i = 1; i <= n - 1; i++) scanf("%d", &d[i]);
  for (i = 1; i <= n - 1; i++) {
    scanf("%d%d", &o, &p);
    add(o, p);
    add(p, o);
  }
  for (i = 1; i <= n; i++)
    for (j = 0; j <= n; j++) f[i][j] = g[i][j] = 1 << 30;
  l = 1;
}
void travel(int x, int u) {
  vist[u] = 1;
  for (int i = sta[u]; i; i = nex[i])
    if (!vist[e[i]]) {
      len[x][e[i]] = len[x][u] + 1;
      travel(x, e[i]);
    }
}
void prepare_len() {
  for (i = 1; i <= n; i++) {
    len[i][i] = 0;
    for (j = 1; j <= n; j++) vist[j] = 0;
    travel(i, i);
  }
  for (i = 1; i <= n; i++) vist[i] = 0;
}
void MakeDrive(int u) {
  vist[u] = 1;
  for (int i = sta[u]; i; i = nex[i])
    if (!vist[e[i]]) {
      n1[++l] = s1[u];
      s1[u] = l;
      e1[l] = e[i];
      MakeDrive(e[i]);
    }
}
void Dp(int u) {
  int i, j, s, o, p, v, sum;
  best[u] = 1 << 30;
  if (!s1[u]) {
    best[u] = f[u][0] = K;
    for (s = 1; s <= n - 1; s++) g[u][s] = d[s];
  } else {
    for (i = s1[u]; i; i = n1[i]) Dp(e1[i]);
    for (s = 0; s <= n - 1; s++) {
      sum = 0;
      for (i = s1[u]; i; i = n1[i]) {
        v = e1[i];
        sum += min(g[v][s + 1], best[v]);
      }
      for (i = s1[u]; i; i = n1[i]) {
        v = e1[i];
        f[u][s] = min(f[u][s], f[v][s - 1] + sum - min(g[v][s + 1], best[v]));
      }
      if (s) {
        g[u][s] = sum + d[s];
        f[u][s] += d[s];
      } else {
        f[u][s] = K + sum;
        g[u][s] = 1 << 30;
      }
      if (f[u][s] < best[u]) {
        best[u] = f[u][s];
        id[u] = s;
      }
    }
  }
}
void dfs(int isf, int u, int s) {
  int i, j, v, sum, t;
  dist[u] = s;
  if (!s) cen[++tot] = u;
  sum = 0;
  for (i = s1[u]; i; i = n1[i]) {
    v = e1[i];
    sum += min(g[v][s + 1], best[v]);
  }
  if (s) {
    if (isf)
      for (i = s1[u]; i; i = n1[i]) {
        v = e1[i];
        if ((f[u][s] - d[s]) ==
            (f[v][s - 1] + sum - min(g[v][s + 1], best[v]))) {
          dfs(1, v, s - 1);
          for (j = s1[u]; j; j = n1[j])
            if (e1[j] != v) {
              t = e1[j];
              if (g[t][s + 1] < best[t])
                dfs(0, t, s + 1);
              else
                dfs(1, t, id[t]);
            }
          break;
        }
      }
    else
      for (i = s1[u]; i; i = n1[i]) {
        t = e1[i];
        if (g[t][s + 1] < best[t])
          dfs(0, t, s + 1);
        else
          dfs(1, t, id[t]);
      }
  } else if (isf)
    for (i = s1[u]; i; i = n1[i]) {
      t = e1[i];
      if (g[t][s + 1] < best[t])
        dfs(0, t, s + 1);
      else
        dfs(1, t, id[t]);
    }
}
void PutAnswer() {
  int ans = 1 << 30, t;
  for (i = 0; i <= n - 1; i++)
    if (f[1][i] < ans) {
      ans = f[1][i];
      t = i;
    }
  cout << ans << endl;
  dfs(1, 1, t);
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= tot; j++)
      if (len[i][cen[j]] == dist[i]) {
        printf("%d", cen[j]);
        break;
      }
    if (i < n)
      printf(" ");
    else
      printf("\n");
  }
}
int main() {
  Init();
  prepare_len();
  MakeDrive(1);
  Dp(1);
  PutAnswer();
  return 0;
}
