#include <bits/stdc++.h>
using namespace std;
const int maxn = 185;
struct Tedge {
  int v;
  Tedge *p;
};
Tedge *head[maxn], buf[maxn * 2], *ptr = buf;
int f[maxn][maxn], dis[maxn][maxn];
int d[maxn], loc[maxn], ans[maxn];
int n, k;
void getdis(int u, int r, int fa) {
  for (Tedge *p = head[u]; p; p = p->p)
    if (p->v != fa) {
      dis[r][p->v] = dis[r][u] + 1;
      getdis(p->v, r, u);
    }
}
void dp(int u, int fa) {
  int i;
  Tedge *p;
  for (i = 1; i <= n; ++i) f[u][i] = d[dis[u][i]] + k;
  for (p = head[u]; p; p = p->p)
    if (p->v != fa) {
      dp(p->v, u);
      for (i = 1; i <= n; ++i)
        f[u][i] += min(f[p->v][i] - k, f[p->v][loc[p->v]]);
    }
  for (i = 1, loc[u] = u; i <= n; ++i)
    if (f[u][i] < f[u][loc[u]]) loc[u] = i;
}
void getans(int u, int r, int fa) {
  Tedge *p;
  ans[u] = r;
  for (p = head[u]; p; p = p->p)
    if (p->v != fa)
      if (f[p->v][r] - k < f[p->v][loc[p->v]])
        getans(p->v, r, u);
      else
        getans(p->v, loc[p->v], u);
}
int main() {
  int i, u, v;
  scanf("%d%d", &n, &k);
  for (i = 1; i < n; ++i) scanf("%d", d + i);
  for (i = 1; i < n; ++i) {
    scanf("%d%d", &u, &v);
    *ptr = (Tedge){v, head[u]};
    head[u] = ptr++;
    *ptr = (Tedge){u, head[v]};
    head[v] = ptr++;
  }
  for (i = 1; i <= n; ++i) getdis(i, i, 0);
  dp(1, 0);
  printf("%d\n", f[1][loc[1]]);
  getans(1, loc[1], 0);
  for (i = 1; i <= n; ++i) printf("%d%c", ans[i], i == n ? '\n' : ' ');
  return 0;
}
