#include <bits/stdc++.h>
using namespace std;
int d[200][200];
int a[200];
int dp[200][200];
int best[200];
int from[200];
vector<int> adia[200];
int n, k;
void calc_from(int nod, int tata, int centru) {
  from[nod] = centru;
  for (auto i : adia[nod]) {
    if (i == tata) continue;
    if (dp[i][best[i]] < dp[i][centru] - k)
      calc_from(i, nod, best[i]);
    else
      calc_from(i, nod, centru);
  }
}
void calc_dp(int nod, int tata) {
  for (int i(1); i <= n; i++) dp[nod][i] = k + a[d[nod][i]];
  for (auto i : adia[nod]) {
    if (i != tata) {
      calc_dp(i, nod);
      for (int j(1); j <= n; j++)
        dp[nod][j] += min(dp[i][best[i]], dp[i][j] - k);
    }
  }
  best[nod] = nod;
  for (int i(1); i <= n; i++)
    if (dp[nod][i] < dp[nod][best[nod]]) best[nod] = i;
}
int main() {
  cin >> n >> k;
  for (int i(1); i < n; i++) cin >> a[i];
  for (int i(1); i <= n; i++)
    for (int j(1); j <= n; j++) d[i][j] = (i != j ? 1e9 : 0);
  int a, b;
  for (int i(1); i < n; i++) {
    cin >> a >> b;
    adia[a].push_back(b);
    adia[b].push_back(a);
    d[a][b] = d[b][a] = 1;
  }
  for (int k(1); k <= n; k++)
    for (int i(1); i <= n; i++)
      for (int j(1); j <= n; j++)
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
  calc_dp(1, 0);
  calc_from(1, 0, best[1]);
  cout << dp[1][best[1]] << '\n';
  for (int i(1); i <= n; i++) cout << from[i] << ' ';
  return 0;
}
