#include <bits/stdc++.h>
using namespace std;
int w[205], d[205][205], f[205][205], b[205], c[205], n, v, x, y;
void dfs(int x, int y) {
  for (int j = 1; j <= n; j++) f[x][j] = w[d[x][j]] + v;
  for (int i = 1; i <= n; i++)
    if (d[x][i] == 1 && y - i) {
      dfs(i, x);
      for (int j = 1; j <= n; j++) f[x][j] += min(f[i][j] - v, f[i][b[i]]);
    }
  b[x] = 1;
  for (int j = 1; j <= n; j++)
    if (f[x][j] < f[x][b[x]]) b[x] = j;
}
void prt(int x, int y, int z) {
  c[x] = z;
  for (int i = 1; i <= n; i++)
    if (d[x][i] == 1 && y - i) prt(i, x, f[i][z] - v < f[i][b[i]] ? z : b[i]);
}
int main() {
  scanf("%d%d", &n, &v);
  for (int i = 1; i <= n - 1; i++) scanf("%d", w + i);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) d[i][j] = (i != j) << 22;
  for (int i = 1; i <= n - 1; i++) scanf("%d%d", &x, &y), d[x][y] = d[y][x] = 1;
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  dfs(1, 0), printf("%d\n", f[1][b[1]]), prt(1, 0, b[1]);
  for (int i = 1; i <= n; i++) printf("%d%s", c[i], i < n ? " " : "\n");
  return 0;
}
