#include <bits/stdc++.h>
const int N = 200;
using namespace std;
struct edge {
  int v, nxt;
} e[N * 2];
int n, k, a[N], head[N], cnt, dep[N], f[N][20];
int p[N], g[N][N], dp[N][N], ans[N];
void adde(int u, int v) {
  e[++cnt].v = v;
  e[cnt].nxt = head[u];
  head[u] = cnt;
}
void dfs(int u, int fa) {
  dep[u] = dep[fa] + 1;
  f[u][0] = fa;
  for (int i = 1; i <= 15; ++i) f[u][i] = f[f[u][i - 1]][i - 1];
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa) continue;
    dfs(v, u);
  }
}
int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 15; i >= 0; --i)
    if (dep[f[u][i]] >= dep[v]) u = f[u][i];
  if (u == v) return u;
  for (int i = 15; i >= 0; --i)
    if (f[u][i] != f[v][i]) {
      u = f[u][i];
      v = f[v][i];
    }
  return f[u][0];
}
int dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
void dfs2(int u, int fa) {
  for (int i = 1; i <= n; ++i) dp[u][i] = a[dis(i, u)] + k;
  p[u] = 1;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa) continue;
    dfs2(v, u);
    for (int j = 1; j <= n; ++j) dp[u][j] += min(dp[v][j] - k, dp[v][p[v]]);
  }
  for (int i = 1; i <= n; ++i)
    if (dp[u][i] < dp[u][p[u]]) p[u] = i;
}
void getans(int u, int fa, int x) {
  ans[u] = x;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa) continue;
    getans(v, u, dp[v][x] - k < dp[v][p[v]] ? x : p[v]);
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; ++i) scanf("%d", &a[i]);
  for (int i = 1, u, v; i < n; ++i) {
    scanf("%d%d", &u, &v);
    adde(u, v);
    adde(v, u);
  }
  dfs(1, 0);
  dfs2(1, 0);
  printf("%d\n", dp[1][p[1]]);
  getans(1, 0, p[1]);
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  return 0;
}
