#include <bits/stdc++.h>
using namespace std;
int n, k, lst[205], to[405], pre[405], tot, cost[205];
int dp[205][205], dis[205][205], pos[205], ans[205];
inline void add_edge(int u, int v) {
  to[tot] = v;
  pre[tot] = lst[u];
  lst[u] = tot++;
}
void dfs(int u, int fa = -1) {
  for (int i = 0; i < n; i++) dp[u][i] = cost[dis[u][i]];
  for (int i = lst[u]; ~i; i = pre[i]) {
    int v = to[i];
    if (v == fa) continue;
    dfs(v, u);
    for (int j = 0; j < n; j++) dp[u][j] += min(dp[v][j], dp[v][pos[v]] + k);
  }
  for (int i = 1; i < n; i++) {
    if (dp[u][i] < dp[u][pos[u]]) pos[u] = i;
  }
}
void upd(int u, int x, int fa = -1) {
  ans[u] = x;
  for (int i = lst[u]; ~i; i = pre[i]) {
    int v = to[i];
    if (v == fa) continue;
    upd(v, dp[v][pos[v]] + k < dp[v][x] ? pos[v] : x, u);
  }
}
int main() {
  memset(lst, -1, sizeof(lst));
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; i++) scanf("%d", cost + i);
  memset(dis, 0x3f, sizeof(dis));
  for (int i = 0; i < n; i++) dis[i][i] = 0;
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    add_edge(--u, --v);
    add_edge(v, u);
    dis[u][v] = dis[v][u] = 1;
  }
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++)
        dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
    }
  }
  dfs(0);
  upd(0, pos[0]);
  printf("%d\n", dp[0][pos[0]] + k);
  for (int i = 0; i < n; i++) printf("%d%c", ans[i] + 1, " \n"[i + 1 == n]);
  return 0;
}
