#include <bits/stdc++.h>
using namespace std;
int n, m, d[200], g[200][200], dp[200][200], ans[200];
int cnt, st[200], ed[200];
bool flag[200];
void dfs1(int u) {
  flag[u] = true;
  st[u] = ++cnt;
  for (int i = 1; i <= n; i++)
    if (g[u][i] == 1 && !flag[i]) dfs1(i);
  ed[u] = ++cnt;
}
void dfs2(int u) {
  flag[u] = true;
  for (int i = 1; i <= n; i++)
    if (i ^ u) dp[u][i] = d[g[u][i]];
  dp[u][u] = m;
  for (int i = 1; i <= n; i++)
    if (g[u][i] == 1 && !flag[i]) {
      dfs2(i);
      for (int j = 1; j <= n; j++)
        if (st[i] <= st[j] && ed[j] <= ed[i])
          dp[u][j] += dp[i][j];
        else
          dp[u][j] += min(dp[i][j], dp[i][dp[i][0]]);
    }
  dp[u][0] = u;
  for (int i = 1; i <= n; i++)
    if (st[u] <= st[i] && ed[i] <= ed[u] && dp[u][i] < dp[u][dp[u][0]])
      dp[u][0] = i;
}
void dfs3(int u) {
  flag[u] = true;
  for (int i = 1; i <= n; i++)
    if (g[u][i] == 1 && !flag[i]) {
      if (st[i] <= st[ans[u]] && ed[ans[u]] <= ed[i])
        ans[i] = ans[u];
      else if (dp[i][ans[u]] < dp[i][dp[i][0]])
        ans[i] = ans[u];
      else
        ans[i] = dp[i][0];
      dfs3(i);
    }
}
void solve() {
  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]);
  memset(flag, false, sizeof(flag));
  cnt = 0;
  dfs1(1);
  memset(flag, false, sizeof(flag));
  dfs2(1);
  ans[1] = dp[1][0];
  memset(flag, false, sizeof(flag));
  dfs3(1);
  printf("%d\n", dp[1][dp[1][0]]);
  for (int i = 1; i <= n; i++) printf("%d%c", ans[i], i < n ? ' ' : '\n');
}
int main() {
  int u, v;
  while (scanf("%d%d", &n, &m) == 2) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) g[i][j] = 1000000000;
    for (int i = 1; i < n; i++) scanf("%d", d + i);
    for (int i = 1; i < n; i++) {
      scanf("%d%d", &u, &v);
      g[u][v] = g[v][u] = 1;
    }
    solve();
  }
  return 0;
}
