#include <bits/stdc++.h>
using namespace std;
int ecnt;
struct Edge {
  int to;
  Edge *next;
} * mat[205], edges[205 * 2];
void link(int x, int to) {
  edges[ecnt].to = to;
  edges[ecnt].next = mat[x];
  mat[x] = &edges[ecnt++];
}
int n, K, dp[205][205], best[205][205];
int d[205], dis[205][205], ans[205];
void dfs(int x, int father, int dis[]) {
  for (Edge *p = mat[x]; p; p = p->next) {
    int to = p->to;
    if (father == to) continue;
    dis[to] = dis[x] + 1;
    dfs(to, x, dis);
  }
}
void solve(int x, int father) {
  for (Edge *p = mat[x]; p; p = p->next) {
    int to = p->to;
    if (father == to) continue;
    solve(to, x);
  }
  for (int i = 1; i <= n; i++) {
    dp[x][i] = d[dis[x][i]];
    for (Edge *p = mat[x]; p; p = p->next) {
      int to = p->to;
      dp[x][i] += min(dp[to][i], dp[to][best[to][i]] + K);
    }
  }
  int g = 1, h = 2;
  if (dp[x][g] > dp[x][h]) swap(g, h);
  for (int i = 3; i <= n; i++)
    if (dp[x][i] < dp[x][g])
      h = g, g = i;
    else if (dp[x][i] < dp[x][h])
      h = i;
  for (int i = 1; i <= n; i++) best[x][i] = i == g ? h : g;
}
void get(int x, int father, int root) {
  ans[x] = root;
  for (Edge *p = mat[x]; p; p = p->next) {
    int to = p->to;
    if (to == father) continue;
    if (dp[to][root] < dp[to][best[to][root]] + K)
      get(to, x, root);
    else
      get(to, x, best[to][root]);
  }
}
int main() {
  scanf("%d%d", &n, &K);
  for (int i = 1; i < n; i++) scanf("%d", &d[i]);
  for (int i = 1, x, y; i < n; i++) {
    scanf("%d%d", &x, &y);
    link(x, y), link(y, x);
  }
  for (int i = 1; i <= n; i++) dfs(i, -1, dis[i]);
  solve(1, -1);
  int g = 1;
  for (int i = 1; i <= n; i++)
    if (dp[1][i] < dp[1][g]) g = i;
  printf("%d\n", dp[1][g] + K);
  get(1, -1, g);
  for (int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n ? '\n' : ' ');
  return 0;
}
