#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int k, dis[185][185];
int n, a[185];
int dp[185][185];
int mini[185], lst[185], co[185][185], fa[185];
bool vis[185];
vector<int> v[185];
void dfs(int p, int start) {
  for (auto u : v[p])
    if (!vis[u]) {
      vis[u] = 1;
      dis[start][u] = dis[start][p] + 1;
      dfs(u, start);
    }
}
void get(int x) {
  for (auto u : v[x])
    if (u != fa[x]) {
      fa[u] = x;
      get(u);
    }
  mini[x] = 1e9;
  for (int to = 1; to <= n; to++) {
    dp[x][to] = a[dis[to][x]] + k;
    for (auto u : v[x])
      if (u != fa[x]) {
        if (mini[u] < dp[u][to] - k) {
          co[to][u] = lst[u];
          dp[x][to] += mini[u];
        } else {
          co[to][u] = to;
          dp[x][to] += dp[u][to] - k;
        }
      }
    if (mini[x] > dp[x][to]) {
      mini[x] = dp[x][to];
      lst[x] = to;
    }
  }
}
int pr[185];
void getpr(int x, int now) {
  pr[x] = now;
  for (auto u : v[x])
    if (u != fa[x]) {
      getpr(u, co[now][u]);
    }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i < n; i++) cin >> a[i];
  int x, y;
  for (int i = 1; i < n; i++) {
    cin >> x >> y;
    v[x].emplace_back(y);
    v[y].emplace_back(x);
  }
  for (int i = 1; i <= n; i++) {
    memset(vis, 0, sizeof(vis));
    vis[i] = 1;
    dfs(i, i);
  }
  get(1);
  int ans = 1;
  for (int i = 2; i <= n; i++) {
    if (dp[1][i] < dp[1][ans]) ans = i;
  }
  cout << dp[1][ans] << '\n';
  getpr(1, ans);
  for (int i = 1; i <= n; i++) cout << pr[i] << ' ';
  return 0;
}
