#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int INF = 1234567890;
int n, costK;
int D[maxn], dis[maxn][maxn];
vector<int> vec[maxn];
int dp[maxn][maxn], best[maxn];
void dfs(int v, int f) {
  for (int i = 0; i < (int)vec[v].size(); i++) {
    int x = vec[v][i];
    if (x != f) dfs(x, v);
  }
  int tm = INF;
  for (int i = 0; i < n; i++) {
    dp[v][i] = D[dis[v][i]];
    for (int j = 0; j < (int)vec[v].size(); j++) {
      int x = vec[v][j];
      if (x == f) continue;
      dp[v][i] += min(dp[x][i], dp[x][best[x]] + costK);
    }
    if (dp[v][i] < tm) {
      tm = dp[v][i];
      best[v] = i;
    }
  }
}
int center[maxn];
void getCenter(int v, int f, int b) {
  center[v] = b;
  for (int i = 0; i < (int)vec[v].size(); i++) {
    int x = vec[v][i];
    if (x == f) continue;
    getCenter(x, v, dp[x][b] > dp[x][best[x]] + costK ? best[x] : b);
  }
}
int main() {
  scanf("%d%d", &n, &costK);
  for (int i = 1; i < n; i++) scanf("%d", &D[i]);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dis[i][j] = (i == j ? 0 : maxn);
    }
  }
  for (int i = 0; i < n - 1; i++) {
    int t1, t2;
    scanf("%d%d", &t1, &t2);
    t1--;
    t2--;
    vec[t1].push_back(t2);
    vec[t2].push_back(t1);
    dis[t1][t2] = dis[t2][t1] = 1;
  }
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
      }
    }
  }
  dfs(0, -1);
  printf("%d\n", dp[0][best[0]] + costK);
  getCenter(0, -1, best[0]);
  for (int i = 0; i < n; i++) {
    if (i != 0) printf(" ");
    printf("%d", center[i] + 1);
  }
  printf("\n");
  return 0;
}
