#include <bits/stdc++.h>
using namespace std;
int n, k;
const int N = 201;
const int INF = 1e9;
vector<int> G[N];
set<int> se[N];
int d[N], dep[N], fa[N][11], dist[N][N], dp[N][N], dp2[N], bes[N], ans[N];
void dfs_dep(int x, int F) {
  fa[x][0] = F;
  for (int i = 1; i <= 10; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
  dep[x] = dep[F] + 1;
  se[x].insert(x);
  for (int i = 0; i < G[x].size(); i++) {
    int tmp = G[x][i];
    if (tmp == F) continue;
    dfs_dep(tmp, x);
    for (set<int>::iterator it = se[tmp].begin(); it != se[tmp].end(); it++) {
      se[x].insert(*it);
    }
  }
}
int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = 10; i >= 0; i--) {
    if (dep[x] - dep[y] >= (1 << i)) x = fa[x][i];
  }
  if (x == y) return x;
  for (int i = 10; i >= 0; i--) {
    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
  }
  return fa[x][0];
}
void dfs_dp(int x, int F) {
  for (int i = 0; i < G[x].size(); i++) {
    int tmp = G[x][i];
    if (tmp == F) continue;
    dfs_dp(tmp, x);
  }
  dp2[x] = INF;
  for (int i = 1; i <= n; i++) {
    if (x == i) dp[x][x] += k;
    dp[x][i] += d[dep[x] + dep[i] - 2 * dep[lca(x, i)]];
    for (int j = 0; j < G[x].size(); j++) {
      int tmp = G[x][j];
      if (tmp == F) continue;
      if (se[tmp].count(i))
        dp[x][i] += dp[tmp][i];
      else if (dp2[tmp] < dp[tmp][i])
        dp[x][i] += dp2[tmp];
      else
        dp[x][i] += dp[tmp][i];
    }
    if (se[x].count(i) && dp2[x] > dp[x][i]) dp2[x] = dp[x][i], bes[x] = i;
  }
}
void pr(int x, int F, int ne) {
  ans[x] = ne;
  for (int i = 0; i < G[x].size(); i++) {
    int tmp = G[x][i];
    if (tmp == F) continue;
    if (se[tmp].count(ne))
      pr(tmp, x, ne);
    else if (dp2[tmp] <= dp[tmp][ne])
      pr(tmp, x, bes[tmp]);
    else
      pr(tmp, x, ne);
  }
}
int main() {
  cin >> n >> k;
  for (int i = 1; i < n; i++) cin >> d[i];
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs_dep(1, 0);
  dfs_dp(1, 0);
  int minv = INF, mini = 0;
  for (int i = 1; i <= n; i++) {
    if (dp[1][i] < minv) minv = dp[1][i], mini = i;
  }
  pr(1, 0, mini);
  cout << minv << endl;
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
  cout << endl;
  return 0;
}
