#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int d[N][N], f[N][N], g[N][N], Min[N], w[N], ans[N], i, j, k, x, y, n;
void floyed() {
  int i, j, z;
  for (z = 1; z <= n; z++)
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        if (z != i && i != j && j != z)
          if (d[i][z] + d[z][j] < d[i][j]) d[i][j] = d[i][z] + d[z][j];
  for (i = 1; i <= n; i++) d[i][i] = 0;
}
void dfs(int u, int fa) {
  int i, j;
  for (i = 1; i <= n; i++) f[u][i] = w[d[u][i]] + k;
  for (i = 1; i <= n; i++)
    if (i != fa && g[u][i] == 1) {
      dfs(i, u);
      for (j = 1; j <= n; j++) f[u][j] += min(f[i][j] - k, f[i][Min[i]]);
    }
  Min[u] = 1;
  for (i = 2; i <= n; i++)
    if (f[u][i] < f[u][Min[u]]) Min[u] = i;
}
void write(int u, int fa, int now) {
  ans[u] = now;
  int i;
  for (i = 1; i <= n; i++)
    if (i != fa && g[u][i] == 1) {
      if (f[i][now] - k < f[i][Min[i]])
        write(i, u, now);
      else
        write(i, u, Min[i]);
    }
}
int main() {
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n - 1; i++) scanf("%d", &w[i]);
  for (i = 1; i <= N; i++)
    for (j = 1; j <= N; j++) d[i][j] = 1e9;
  for (i = 1; i <= n - 1; i++) {
    scanf("%d%d", &x, &y);
    g[x][y] = g[y][x] = d[x][y] = d[y][x] = 1;
  }
  floyed();
  dfs(1, 0);
  printf("%d\n", f[1][Min[1]]);
  write(1, 0, Min[1]);
  for (i = 1; i <= n; i++) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}
