#include <bits/stdc++.h>
using namespace std;
template <class T>
void chmax(T &x, T y) {
  x = x > y ? x : y;
}
template <class T>
void chmin(T &x, T y) {
  x = x < y ? x : y;
}
const int maxn = 205;
int n, k;
int d[maxn], ans[maxn], choice[maxn];
int dp[maxn][maxn];
int dist[maxn][maxn];
vector<int> v[maxn];
void predfs(int pos, int fa, int *dis) {
  for (int i = 0; i < (int)(v[pos]).size(); i++) {
    int to = v[pos][i];
    if (to == fa) continue;
    dis[to] = dis[pos] + 1;
    predfs(to, pos, dis);
  }
}
void dfs(int pos, int fa) {
  for (int i = 1; i <= n; i++) dp[pos][i] = d[dist[pos][i]] + k;
  for (int i = 0; i < (int)(v[pos]).size(); i++) {
    int to = v[pos][i];
    if (to == fa) continue;
    dfs(to, pos);
    for (int j = 1; j <= n; j++)
      dp[pos][j] += min(dp[to][choice[to]], dp[to][j] - k);
  }
  choice[pos] = min_element(dp[pos] + 1, dp[pos] + n + 1) - dp[pos];
  return;
}
void print(int pos, int fa, int j) {
  for (int i = 0, _j; i < (int)(v[pos]).size(); i++) {
    int to = v[pos][i];
    if (to == fa) continue;
    if (dp[to][choice[to]] < dp[to][j] - k) {
      _j = choice[to];
    } else {
      _j = j;
    }
    ans[to] = _j;
    print(to, pos, _j);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n - 1; i++) cin >> d[i];
  for (int i = 1; i <= n - 1; i++) {
    int x, y;
    cin >> x >> y;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  for (int i = 1; i <= n; i++) predfs(i, 0, dist[i]);
  dfs(1, 0);
  cout << dp[1][choice[1]] << endl;
  print(1, 0, choice[1]);
  ans[1] = choice[1];
  for (int i = 1; i <= n; i++) cout << ans[i] << " ";
  cout << endl;
  return 0;
}
