#include <bits/stdc++.h>
using namespace std;
struct edge {
  int to, next;
} e[183 << 1];
int head[183], cnte;
void add(int u, int v) {
  e[++cnte].to = v;
  e[cnte].next = head[u];
  head[u] = cnte;
}
int n, k, d[183], dis[183][183], dp[183][183], mi[183], ANS[183];
void dfs(int u, int last) {
  for (int i = 1; i <= n; i++) dp[u][i] = d[dis[u][i]] + k;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v == last) continue;
    dfs(v, u);
    for (int j = 1; j <= n; j++) {
      dp[u][j] += min(dp[v][j] - k, dp[v][mi[v]]);
    }
  }
  mi[u] = 1;
  for (int i = 2; i <= n; i++) {
    if (dp[u][i] < dp[u][mi[u]]) mi[u] = i;
  }
}
void init(int u, int last, int A) {
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v == last) continue;
    dis[A][v] = dis[A][u] + 1;
    init(v, u, A);
  }
}
void output(int u, int last, int Mi) {
  ANS[u] = Mi;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v == last) continue;
    if (dp[v][mi[v]] < dp[v][Mi] - k)
      output(v, u, mi[v]);
    else
      output(v, u, Mi);
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; i++) scanf("%d", d + i);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    add(u, v);
    add(v, u);
  }
  for (int i = 1; i <= n; i++) init(i, 0, i);
  dfs(1, 0);
  printf("%d\n", dp[1][mi[1]]);
  output(1, 0, mi[1]);
  for (int i = 1; i <= n; i++) printf("%d ", ANS[i]);
  return 0;
}
