#include <bits/stdc++.h>
using namespace std;
int i, j, k, l, n, m, s, an, sum, tot, K;
int dis[500][500], v[500], e[1000], nxt[1000], go[1000];
int dp[500][500], best[500][500], ans[500];
void add(int x, int y) {
  tot++;
  e[tot] = y;
  nxt[tot] = go[x];
  go[x] = tot;
}
void dfs(int x, int pre, int now) {
  for (int p = go[x]; p; p = nxt[p]) {
    if (e[p] != pre) {
      int y = e[p];
      dis[now][y] = dis[now][x] + 1;
      dfs(y, x, now);
    }
  }
}
void work(int x, int pre) {
  for (int p = go[x]; p; p = nxt[p])
    if (e[p] != pre) work(e[p], x);
  for (int i = 1; i <= n; i++) {
    dp[x][i] = v[dis[x][i]];
    for (int p = go[x]; p; p = nxt[p]) {
      if (e[p] != pre) {
        int y = e[p];
        dp[x][i] += min(dp[y][i], dp[y][best[y][i]] + K);
      }
    }
  }
  int k = 1;
  for (int i = 2; i <= n; i++)
    if (dp[x][i] < dp[x][k]) k = i;
  for (int i = 1; i <= n; i++) best[x][i] = k;
}
void find(int x, int pre, int now) {
  ans[x] = now;
  for (int p = go[x]; p; p = nxt[p]) {
    if (e[p] != pre) {
      int y = e[p];
      if (dp[y][now] < dp[y][best[y][now]] + K)
        find(y, x, now);
      else
        find(y, x, best[y][now]);
    }
  }
}
int main() {
  scanf("%d %d", &n, &K);
  for (int i = 1; i < n; i++) scanf("%d", &v[i]);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    add(x, y);
    add(y, x);
  }
  for (int i = 1; i <= n; i++) dfs(i, -1, i);
  work(1, -1);
  int k = 1;
  for (int i = 2; i <= n; i++)
    if (dp[1][i] < dp[1][k]) k = i;
  find(1, -1, k);
  printf("%d\n", dp[1][k] + K);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  return 0;
}
