#include <bits/stdc++.h>
int c[200];
int co[200][200];
int ma[200][200], mp[200];
int u[200];
int pr[200];
int di[200][200];
int dp[200][200];
int K, n;
void dfs(int x) {
  int i;
  for (i = 0; i < mp[x]; i++) {
    if (!u[ma[x][i]]) {
      u[ma[x][i]] = 1;
      pr[ma[x][i]] = x;
      dfs(ma[x][i]);
    }
  }
}
int calc(int x, int y) {
  if (dp[x][y] != -1) return dp[x][y];
  int i, j, z, d, md;
  dp[x][y] = c[co[x][y]] + K;
  for (i = 0; i < mp[x]; i++) {
    if ((z = ma[x][i]) == pr[x]) continue;
    md = 100000000;
    for (j = 0; j < n; j++) {
      d = calc(z, j);
      if (j == y) d -= K;
      if (d < md) md = d;
    }
    dp[x][y] += md;
  }
  return dp[x][y];
}
void fill(int x, int y) {
  int i, j, z, md, d, mj;
  u[x] = y;
  for (i = 0; i < mp[x]; i++) {
    if ((z = ma[x][i]) == pr[x]) continue;
    md = 100000000;
    for (j = 0; j < n; j++) {
      d = calc(z, j);
      if (j == y) d -= K;
      if (d < md) {
        md = d;
        mj = j;
      }
    }
    fill(z, mj);
  }
}
int main() {
  int i, j, k, x, y, z, md, mi;
  scanf("%d %d", &n, &K);
  for (i = 1; i < n; i++) {
    scanf("%d", &c[i]);
  }
  c[0] = 0;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      co[i][j] = 100000000;
    }
    co[i][i] = 0;
  }
  for (i = 1; i < n; i++) {
    scanf("%d %d", &x, &y);
    x--;
    y--;
    ma[x][mp[x]++] = y;
    ma[y][mp[y]++] = x;
    co[x][y] = co[y][x] = 1;
  }
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      for (k = 0; k < n; k++) {
        if (co[j][i] + co[i][k] < co[j][k]) {
          co[j][k] = co[j][i] + co[i][k];
        }
      }
    }
  }
  u[0] = 1;
  dfs(0);
  pr[0] = -1;
  md = 100000000;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      dp[i][j] = -1;
    }
  }
  for (i = 0; i < n; i++) {
    z = calc(0, i);
    if (z < md) {
      md = z;
      mi = i;
    }
  }
  fill(0, mi);
  printf("%d\n", md);
  for (i = 0; i < n; i++) {
    printf("%d%c", u[i] + 1, i == n - 1 ? '\n' : ' ');
  }
  return 0;
}
