#include <bits/stdc++.h>
using namespace std;
int n, m, a[202], c[201], dis[201][201], f[201][202], ans[202];
void dfs(int x, int fa) {
  int i, j;
  for (i = 1; i <= n; i++) f[x][i] = c[dis[x][i]] + m;
  for (i = 1; i <= n; i++)
    if (dis[x][i] == 1 && i != fa) {
      dfs(i, x);
      for (j = 1; j <= n; j++) f[x][j] += min(f[i][j] - m, f[i][ans[i]]);
    }
  ans[x] = 1;
  for (i = 2; i <= n; i++)
    if (f[x][i] < f[x][ans[x]]) ans[x] = i;
}
void get(int x, int fa, int now) {
  a[x] = now;
  int i;
  for (i = 1; i <= n; i++)
    if (dis[x][i] == 1 && i != fa) {
      if (f[i][now] - m < f[i][ans[i]])
        get(i, x, now);
      else
        get(i, x, ans[i]);
    }
}
int main() {
  int i, j, x, y, k;
  scanf("%d%d", &n, &m);
  for (i = 1; i < n; i++) scanf("%d", &c[i]);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      if (i == j)
        dis[i][j] = 0;
      else
        dis[i][j] = 1e9;
  for (i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    dis[x][y] = dis[y][x] = 1;
  }
  for (k = 1; k <= n; k++)
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  dfs(1, 0);
  printf("%d\n", f[1][ans[1]]);
  get(1, 0, ans[1]);
  for (i = 1; i <= n; i++) printf("%d ", a[i]);
}
