#include <bits/stdc++.h>
int fr[182], ne[362], v[362], bs = 0;
void addb(int a, int b) {
  v[bs] = b;
  ne[bs] = fr[a];
  fr[a] = bs++;
}
int dp[182][182], wz[182], sz[182], cd[182][182], n, k;
int fa[182], sd[182], ans[182], zy[362][182];
void dfs0(int u, int f) {
  fa[u] = f;
  sd[u] = sd[f] + 1;
  for (int i = fr[u]; i != -1; i = ne[i]) {
    if (v[i] != f) dfs0(v[i], u);
  }
}
int dfscd(int a, int b) {
  if (a == b) return 0;
  if (cd[a][b]) return cd[a][b];
  if (sd[a] > sd[b])
    cd[a][b] = dfscd(fa[a], b) + 1;
  else
    cd[a][b] = dfscd(a, fa[b]) + 1;
  return cd[a][b];
}
void dfs(int u, int f) {
  for (int i = fr[u]; i != -1; i = ne[i]) {
    if (v[i] != f) dfs(v[i], u);
  }
  for (int a = 1; a <= n; a++) {
    dp[u][a] = sz[cd[u][a]] + k;
    for (int i = fr[u]; i != -1; i = ne[i]) {
      if (v[i] == f) continue;
      int t = dp[v[i]][wz[v[i]]];
      if (dp[v[i]][a] - k < t) {
        t = dp[v[i]][a] - k;
        zy[i][a] = a;
      } else
        zy[i][a] = wz[v[i]];
      dp[u][a] += t;
    }
    if (a == 1 || dp[u][a] < dp[u][wz[u]]) wz[u] = a;
  }
}
void dfs1(int u, int f, int a) {
  ans[u] = a;
  for (int i = fr[u]; i != -1; i = ne[i]) {
    if (v[i] != f) dfs1(v[i], u, zy[i][a]);
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) fr[i] = -1;
  for (int i = 1; i < n; i++) scanf("%d", &sz[i]);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    addb(a, b);
    addb(b, a);
  }
  dfs0(1, 0);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i != j && cd[i][j] == 0) dfscd(i, j);
    }
  }
  dfs(1, 0);
  int z = 1;
  for (int i = 2; i <= n; i++) {
    if (dp[1][i] < dp[1][z]) z = i;
  }
  printf("%d\n", dp[1][z]);
  dfs1(1, 0, z);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  return 0;
}
