#include <bits/stdc++.h>
using namespace std;
int dis[190][190];
vector<int> G[190];
int dp[190][190];
int d[190];
int opt[190];
int ans[190];
int n, k;
void dfs(int x, int p, int rt) {
  for (int i = 0; i < (int)G[x].size(); i++) {
    int y = G[x][i];
    if (y == p) continue;
    dis[rt][y] = dis[rt][x] + 1;
    dfs(y, x, rt);
  }
}
void solve(int x, int p) {
  for (int i = 1; i <= n; i++) dp[x][i] = d[dis[x][i]];
  for (int i = 0; i < (int)G[x].size(); i++) {
    int y = G[x][i];
    if (y == p) continue;
    solve(y, x);
    for (int j = 1; j <= n; j++) dp[x][j] += min(dp[y][j], dp[y][opt[y]] + k);
  }
  for (int i = 1; i <= n; i++) {
    if (!opt[x] || dp[x][i] < dp[x][opt[x]]) opt[x] = i;
  }
}
void getans(int x, int p, int col) {
  ans[x] = col;
  for (int i = 0; i < (int)G[x].size(); i++) {
    int y = G[x][i];
    if (y == p) continue;
    int ncol = col;
    if (dp[y][opt[y]] + k < dp[y][col]) ncol = opt[y];
    getans(y, x, ncol);
  }
}
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++) {
    int x, y;
    scanf("%d%d", &x, &y);
    G[x].push_back(y);
    G[y].push_back(x);
  }
  for (int i = 1; i <= n; i++) dfs(i, 0, i);
  solve(1, 0);
  printf("%d\n", dp[1][opt[1]] + k);
  getans(1, 0, opt[1]);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  return 0;
}
