#include <bits/stdc++.h>
using namespace std;
const int mn = 210, inf = 1 << 29;
int d[mn], c[mn], ans[mn], f[mn][mn], g[mn][mn];
int n, co;
void dp(int r, int fa) {
  int i, j;
  for (i = 1; i <= n; ++i) f[r][i] = d[g[r][i]] + co;
  for (i = 1; i <= n; ++i) {
    if (g[r][i] != 1 || i == fa) continue;
    dp(i, r);
    for (j = 1; j <= n; ++j) f[r][j] += min(f[i][j] - co, f[i][c[i]]);
  }
  c[r] = r;
  for (i = 1; i <= n; ++i)
    if (f[r][i] < f[r][c[r]]) c[r] = i;
}
void repair(int r, int fa, int k) {
  int i;
  ans[r] = k;
  for (i = 1; i <= n; ++i) {
    if (g[r][i] != 1 || i == fa) continue;
    if (f[i][k] - co < f[i][c[i]])
      repair(i, r, k);
    else
      repair(i, r, c[i]);
  }
}
int main() {
  int i, j, k;
  scanf("%d%d", &n, &co);
  for (i = 1; i <= n - 1; ++i) scanf("%d", d + i);
  fill(g[1], g[n + 1], inf);
  for (i = 1; i <= n - 1; ++i) {
    scanf("%d%d", &j, &k);
    g[j][k] = g[k][j] = 1;
  }
  for (i = 1; i <= n; ++i) g[i][i] = 0;
  for (k = 1; k <= n; ++k)
    for (i = 1; i <= n; ++i)
      for (j = 1; j <= n; ++j) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
  dp(1, 0);
  printf("%d\n", f[1][c[1]]);
  repair(1, 0, c[1]);
  printf("%d", ans[1]);
  for (i = 2; i <= n; ++i) printf(" %d", ans[i]);
  printf("\n");
  return 0;
}
