#include <bits/stdc++.h>
using namespace std;
int N, K, x, y;
int ans[200], res[200], d[200];
int f[200][200], g[200][200];
void dfs(int x, int fa) {
  for (int i = 1; i <= N; i++) f[x][i] = d[g[x][i]] + K;
  for (int v = 1; v <= N; v++)
    if (g[x][v] == 1 && v != fa) {
      dfs(v, x);
      for (int i = 1; i <= N; i++) f[x][i] += min(f[v][i] - K, f[v][ans[v]]);
    }
  ans[x] = 1;
  for (int i = 2; i <= N; i++)
    if (f[x][i] < f[x][ans[x]]) ans[x] = i;
}
void make(int x, int fa, int cnt) {
  res[x] = cnt;
  for (int i = 1; i <= N; i++)
    if (g[x][i] == 1 && i != fa) {
      int t;
      if (f[i][cnt] - K < f[i][ans[i]])
        t = cnt;
      else
        t = ans[i];
      make(i, x, t);
    }
}
int main() {
  scanf("%d%d", &N, &K);
  for (int i = 1; i < N; i++) scanf("%d", &d[i]);
  memset(g, 20, sizeof(g));
  for (int i = 1; i < N; i++) {
    scanf("%d%d", &x, &y);
    g[x][y] = 1;
    g[y][x] = 1;
  }
  for (int i = 1; i <= N; i++) g[i][i] = 0;
  for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
  dfs(1, 0);
  printf("%d\n", f[1][ans[1]]);
  make(1, 0, ans[1]);
  for (int i = 1; i <= N; i++) printf("%d ", res[i]);
}
