#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, maxn = 185;
int n, K, d[maxn], dis[maxn][maxn], m[maxn][maxn], dp[maxn][maxn], ans[maxn],
    path[maxn];
void dfs(int u, int fa) {
  for (int i = 1; i <= n; i++) dp[u][i] = d[dis[u][i]] + K;
  for (int v = 1; v <= n; v++)
    if (m[u][v] && v != fa) {
      dfs(v, u);
      for (int i = 1; i <= n; i++) dp[u][i] += min(dp[v][ans[v]], dp[v][i] - K);
    }
  ans[u] = 1;
  for (int i = 2; i <= n; i++)
    if (dp[u][i] < dp[u][ans[u]]) ans[u] = i;
}
void output(int u, int fa, int i) {
  path[u] = i;
  for (int v = 1; v <= n; v++)
    if (m[u][v] && v != fa) {
      if (dp[v][ans[v]] < dp[v][i] - K)
        output(v, u, ans[v]);
      else
        output(v, u, i);
    }
}
int main() {
  scanf("%d%d", &n, &K);
  for (int i = 1; i < n; i++) scanf("%d", &d[i]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (i != j)
        dis[i][j] = INF;
      else
        dis[i][j] = 0;
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    m[u][v] = m[v][u] = 1;
    dis[u][v] = dis[v][u] = 1;
  }
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  dfs(1, 0);
  printf("%d\n", dp[1][ans[1]]);
  output(1, 0, ans[1]);
  for (int i = 1; i <= n; i++) printf("%d%c", path[i], i == n ? '\n' : ' ');
  return 0;
}
