#include <bits/stdc++.h>
using namespace std;
int n, m, nn, head[200], a[200][200], belong[200], b[200], dp[200][200], d[200];
struct arr {
  int aa, bb;
} na[400];
int min(int l, int r) {
  if (l < r)
    return l;
  else
    return r;
}
void add(int x, int y) {
  nn = nn + 1;
  na[nn].aa = y;
  na[nn].bb = head[x];
  head[x] = nn;
}
void fdp(int u, int fa) {
  for (int i = 1; i <= n; i++) dp[u][i] = d[a[u][i]];
  for (int i = head[u]; i; i = na[i].bb) {
    int j = na[i].aa;
    if (j == fa) continue;
    fdp(j, u);
    for (int k = 1; k <= n; k++)
      dp[u][k] = dp[u][k] + min(dp[j][b[j]] + m, dp[j][k]);
  }
  b[u] = -1;
  for (int i = 1; i <= n; i++) {
    if (b[u] == -1) {
      b[u] = i;
      continue;
    }
    if (dp[u][i] < dp[u][b[u]]) b[u] = i;
  }
}
void shuchu(int u, int fa, int v) {
  belong[u] = v;
  for (int i = head[u]; i; i = na[i].bb) {
    int j = na[i].aa;
    if (j == fa) continue;
    if (dp[j][b[j]] + m < dp[j][v])
      shuchu(j, u, b[j]);
    else
      shuchu(j, u, v);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n - 1; i++) scanf("%d", &d[i]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (i == j)
        a[i][j] = 0;
      else
        a[i][j] = 2019201920 / 2;
  for (int i = 1; i <= n - 1; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    add(x, y);
    add(y, x);
    a[x][y] = 1;
    a[y][x] = 1;
  }
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if ((k != i) && (k != j) && (i != j))
          a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
  fdp(1, 0);
  printf("%d\n", dp[1][b[1]] + m);
  shuchu(1, 0, b[1]);
  for (int i = 1; i <= n; i++) printf("%d ", belong[i]);
  return 0;
}
