#include <bits/stdc++.h>
using namespace std;
const int DIM = 189;
vector<int> edg[DIM];
int dst[DIM][DIM], cst[DIM];
int dp[DIM][DIM], opt[DIM], ans[DIM];
void dpdfs(int x, int f, int n, int k) {
  for (int y = 1; y <= n; ++y) dp[x][y] = cst[dst[x][y]] + k;
  for (int y : edg[x])
    if (y != f) {
      dpdfs(y, x, n, k);
      for (int z = 1; z <= n; ++z) dp[x][z] += min(dp[y][z] - k, dp[y][opt[y]]);
    }
  opt[x] = 1;
  for (int y = 1; y <= n; ++y)
    if (dp[x][y] < dp[x][opt[x]]) opt[x] = y;
}
void soldfs(int x, int f, int n, int k, int v) {
  ans[x] = v;
  for (int y : edg[x])
    if (y != f) soldfs(y, x, n, k, (dp[y][v] - k < dp[y][opt[y]] ? v : opt[y]));
}
int main(void) {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      if (i != j) dst[i][j] = numeric_limits<int>::max() / 2;
  for (int i = 1; i <= n - 1; ++i) scanf("%d", &cst[i]);
  for (int i = 1; i <= n - 1; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    edg[x].push_back(y);
    dst[x][y] = 1;
    edg[y].push_back(x);
    dst[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 (dst[i][j] > dst[i][k] + dst[k][j])
          dst[i][j] = dst[i][k] + dst[k][j];
  dpdfs(1, 0, n, k);
  soldfs(1, 0, n, k, opt[1]);
  printf("%d\n", dp[1][opt[1]]);
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  return 0;
}
