#include <bits/stdc++.h>
const int N = 210;
const int M = 410;
const int INF = 1e8;
using namespace std;
int n;
int las[N], ans[N];
int edge[M], lst[N], nxt[M], t = 0;
long long dis[N][N], f[N][N], mn[N], d[N], K;
void ADD(int x, int y) {
  edge[++t] = y;
  nxt[t] = lst[x];
  lst[x] = t;
}
void READ() {
  int u, v;
  scanf("%d%lld", &n, &K);
  for (int i = 1; i <= n - 1; i++) scanf("%lld", &d[i]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) dis[i][j] = INF;
  for (int i = 1; i <= n; i++) dis[i][i] = 0;
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d%d", &u, &v);
    ADD(u, v);
    ADD(v, u);
    dis[u][v] = dis[v][u] = 1;
  }
}
void INIT() {
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
      }
    }
  }
  for (int i = 1; i <= n; i++) mn[i] = 1e16, las[i] = -1;
}
void SEARCH(int x, int fa) {
  for (int r = lst[x]; r; r = nxt[r]) {
    if (edge[r] == fa) continue;
    SEARCH(edge[r], x);
  }
  for (int pos = 1; pos <= n; pos++) {
    f[x][pos] = d[dis[x][pos]] + K;
    for (int r = lst[x]; r; r = nxt[r]) {
      if (edge[r] == fa) continue;
      f[x][pos] += min(f[edge[r]][las[edge[r]]], f[edge[r]][pos] - K);
    }
    if (f[x][pos] < mn[x]) las[x] = pos, mn[x] = f[x][pos];
  }
}
void SOLVE(int x, int fa) {
  for (int r = lst[x]; r; r = nxt[r]) {
    if (edge[r] == fa) continue;
    if (f[edge[r]][las[edge[r]]] < f[edge[r]][ans[x]] - K)
      ans[edge[r]] = las[edge[r]];
    else
      ans[edge[r]] = ans[x];
    SOLVE(edge[r], x);
  }
}
int main() {
  READ();
  INIT();
  SEARCH(1, 0);
  printf("%lld\n", mn[1]);
  ans[1] = las[1];
  SOLVE(1, 0);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  return 0;
}
