#include <bits/stdc++.h>
using namespace std;
const int maxn = 200;
const int inf = 1e9 + 10;
int dp[maxn][maxn], d[maxn], dist[maxn][maxn];
vector<pair<int, int> > from[maxn][maxn];
pair<int, int> f[maxn];
vector<int> g[maxn];
int n, k;
void getdist(int root, int x, int fa) {
  for (int i = 0; i < g[x].size(); i++) {
    int to = g[x][i];
    if (to == fa) continue;
    dist[root][to] = dist[root][x] + 1;
    getdist(root, to, x);
  }
}
void getdp(int x, int fa) {
  if (g[x].size() == 1 && fa != -1) {
    for (int i = 0; i < n; i++) {
      dp[x][i] = d[dist[x][i]] + k;
    }
    f[x] = make_pair(inf, -1);
    for (int i = 0; i < n; i++) {
      if (f[x].first > dp[x][i]) {
        f[x].first = dp[x][i];
        f[x].second = i;
      }
    }
    return;
  }
  for (int i = 0; i < n; i++) dp[x][i] = 0;
  for (int i = 0; i < g[x].size(); i++) {
    int to = g[x][i];
    if (to == fa) continue;
    getdp(to, x);
    for (int j = 0; j < n; j++) {
      if (dp[to][j] - k <= f[to].first) {
        dp[x][j] += dp[to][j] - k;
        from[x][j].push_back(make_pair(to, j));
      } else {
        dp[x][j] += f[to].first;
        from[x][j].push_back(make_pair(to, f[to].second));
      }
    }
  }
  f[x] = make_pair(inf, -1);
  for (int i = 0; i < n; i++) {
    dp[x][i] += d[dist[x][i]] + k;
    if (dp[x][i] < f[x].first) {
      f[x].first = dp[x][i];
      f[x].second = i;
    }
  }
}
bool station[maxn];
void getans(int x, int t) {
  station[t] = 1;
  if (from[x][t].size() == 0) return;
  for (int i = 0; i < from[x][t].size(); i++) {
    int to = from[x][t][i].first, id = from[x][t][i].second;
    getans(to, id);
  }
}
int main() {
  for (int i = 0; i < maxn; i++)
    for (int j = 0; j < maxn; j++) dp[i][j] = inf;
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; i++) scanf("%d", &d[i]);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--;
    v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 0; i < n; i++) getdist(i, i, -1);
  getdp(0, -1);
  int ans = inf, id = -1;
  for (int i = 0; i < n; i++) {
    if (dp[0][i] < ans) {
      ans = dp[0][i];
      id = i;
    }
  }
  getans(0, id);
  printf("%d\n", ans);
  for (int i = 0; i < n; i++) {
    int dis = inf, id = -1;
    for (int j = 0; j < n; j++)
      if (station[j]) {
        if (dist[i][j] < dis) {
          dis = dist[i][j];
          id = j;
        }
      }
    printf("%d ", id + 1);
  }
  printf("\n");
  return 0;
}
