#include <bits/stdc++.h>
using namespace std;
vector<long long> e[301];
long long n, k, d[301], f[301][301], dp[301][301], mini[301], wwk[301];
void tr_dp(long long x, long long dd) {
  for (long long i = 1; i <= n; i++) dp[x][i] = d[f[x][i]] + k;
  for (long long i = 0; i < e[x].size(); i++) {
    long long y = e[x][i];
    if (dd == y) continue;
    tr_dp(y, x);
    for (long long j = 1; j <= n; j++)
      dp[x][j] += min(dp[y][mini[y]], dp[y][j] - k);
  }
  mini[x] = 1;
  for (long long i = 2; i <= n; i++)
    if (dp[x][i] < dp[x][mini[x]]) mini[x] = i;
}
void tr_put(long long x, long long dd, long long ff) {
  wwk[x] = ff;
  for (long long i = 0; i < e[x].size(); i++) {
    long long y = e[x][i];
    if (y == dd) continue;
    if (dp[y][mini[y]] < dp[y][ff] - k)
      tr_put(y, x, mini[y]);
    else
      tr_put(y, x, ff);
  }
}
int main() {
  scanf("%lld%lld", &n, &k);
  for (long long i = 1; i < n; i++) scanf("%lld", &d[i]);
  memset(f, 0x3f3f3f3f, sizeof(f));
  for (long long i = 1; i <= n; i++) f[i][i] = 0;
  for (long long i = 1; i < n; i++) {
    long long a, b;
    scanf("%lld%lld", &a, &b);
    e[a].push_back(b);
    e[b].push_back(a);
    f[a][b] = 1;
    f[b][a] = 1;
  }
  for (long long k = 1; k <= n; k++)
    for (long long i = 1; i <= n; i++)
      for (long long j = 1; j <= n; j++)
        f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
  tr_dp(1, 0);
  printf("%lld\n", dp[1][mini[1]]);
  tr_put(1, 0, mini[1]);
  for (long long i = 1; i <= n; i++) printf("%lld ", wwk[i]);
}
