#include <bits/stdc++.h>
using namespace std;
int f[185][185], best[185], dis[185][185], cost[185], n, k, d[185][185],
    ans[185];
void floyd() {
  for (int i = 1; i <= n; i++) dis[i][i] = 0;
  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]);
}
void dp(int x, int fa) {
  for (int y = 1; y <= n; y++)
    if (d[x][y])
      if (y != fa) dp(y, x);
  for (int i = 1, minn = 1 << 30; i <= n; i++) {
    f[x][i] = cost[dis[x][i]] + k;
    for (int y = 1; y <= n; y++)
      if (d[x][y])
        if (y != fa) f[x][i] += min(f[y][i] - k, f[y][best[y]]);
    if (f[x][i] < minn) {
      minn = f[x][i];
      best[x] = i;
    }
  }
}
void make(int x, int fa) {
  for (int y = 1; y <= n; y++)
    if (d[x][y])
      if (y != fa) {
        if (f[y][best[y]] < f[y][ans[x]] - k)
          ans[y] = best[y];
        else
          ans[y] = ans[x];
        make(y, x);
      }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; i++) scanf("%d", &cost[i]);
  memset(dis, 63, sizeof(dis));
  for (int i = 1, a, b; i < n; i++) {
    scanf("%d%d", &a, &b);
    d[a][b] = d[b][a] = true;
    dis[a][b] = dis[b][a] = 1;
  }
  floyd();
  dp(1, 0);
  ans[1] = best[1];
  make(1, 0);
  printf("%d\n", f[1][best[1]]);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}
