#include <bits/stdc++.h>
using namespace std;
long long n, k, f[190][190], a[190], d[190][190], ans[190], pre[190];
vector<long long> edge[190];
inline void floyd() {
  for (long long k = 1; k <= n; k++) {
    for (long long i = 1; i <= n; i++) {
      for (long long j = 1; j <= n; j++) {
        d[i][j] = d[j][i] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
}
void dfs(long long m, long long before) {
  for (long long i = 1; i <= n; i++) f[m][i] = a[d[m][i]] + k;
  for (long long i = 0; i < edge[m].size(); i++) {
    long long Next = edge[m][i];
    if (Next != before) {
      dfs(Next, m);
      for (long long j = 1; j <= n; j++)
        f[m][j] += min(f[Next][ans[Next]], f[Next][j] - k);
    }
  }
  ans[m] = 1;
  for (long long i = 2; i <= n; i++) {
    if (f[m][i] < f[m][ans[m]]) ans[m] = i;
  }
}
void print(long long m, long long before, long long x) {
  pre[m] = x;
  for (long long i = 0; i < edge[m].size(); i++) {
    long long Next = edge[m][i];
    if (Next != before) {
      if (f[Next][ans[Next]] < f[Next][x] - k)
        print(Next, m, ans[Next]);
      else
        print(Next, m, x);
    }
  }
}
int main() {
  cin >> n >> k;
  for (long long i = 1; i < n; i++) scanf("%lld", &a[i]);
  memset(d, 0x3f, sizeof(d));
  for (long long i = 1; i <= n; i++) d[i][i] = 0;
  for (long long i = 1; i < n; i++) {
    long long x, y;
    scanf("%lld %lld", &x, &y);
    d[x][y] = d[y][x] = 1;
    edge[x].push_back(y);
    edge[y].push_back(x);
  }
  floyd();
  dfs(1, 0);
  printf("%lld\n", f[1][ans[1]]);
  print(1, 0, ans[1]);
  for (long long i = 1; i <= n; i++) printf("%lld ", pre[i]);
  return 0;
}
