#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, K, d[190], dis[190][190], m[190][190], dp[190][190], ans[190], path[190];
void dfs(int np, int fa) {
  for (int i = 1; i <= n; i++) dp[np][i] = d[dis[np][i]] + K;
  for (int i = 1; i <= n; i++) {
    if (m[np][i] && i != fa) {
      dfs(i, np);
      for (int j = 1; j <= n; j++)
        dp[np][j] += min(dp[i][ans[i]], dp[i][j] - K);
    }
  }
  ans[np] = 1;
  for (int i = 2; i <= n; i++)
    if (dp[np][i] < dp[np][ans[np]]) ans[np] = i;
}
void output(int np, int fa, int x) {
  path[np] = x;
  for (int i = 1; i <= n; i++) {
    if (m[np][i] && i != fa) {
      if (dp[i][ans[i]] < dp[i][x] - K)
        output(i, np, ans[i]);
      else
        output(i, np, x);
    }
  }
}
int main() {
  scanf("%d%d", &n, &K);
  for (int i = 1; i < n; i++) scanf("%d", &d[i]);
  memset(dis, 0x3f, sizeof(dis));
  for (int i = 1; i <= n; i++) dis[i][i] = 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 ", path[i]);
  return 0;
}
