#include <bits/stdc++.h>
using namespace std;
const int N = 200, INF = 1e9;
int dp[N][N], dis[N][N], dpd[N][N], st[N], en[N], d[N], n, k, cur_time;
int ans[N][N], out[N];
vector<int> g[N];
void dfs_dis(int root, int v, int par = -1) {
  dis[root][v] = (v == root ? 0 : dis[root][par] + 1);
  for (auto u : g[v])
    if (u != par) dfs_dis(root, u, v);
}
void dfs_prep(int v = 0, int par = -1) {
  st[v] = cur_time++;
  for (auto u : g[v])
    if (u != par) dfs_prep(u, v);
  en[v] = cur_time;
}
bool isPar(int v, int u) { return (st[v] <= st[u] && en[u] <= en[v]); }
void dfs(int v = 0, int par = -1) {
  for (auto u : g[v])
    if (u != par) dfs(u, v);
  for (int i = 0; i <= n - 1; i++) dpd[v][i] = INF;
  for (int from = 0; from < n; from++) {
    dp[v][from] = d[dis[v][from]];
    for (auto u : g[v]) {
      if (u == par) continue;
      if (isPar(u, from))
        dp[v][from] += dp[u][from];
      else {
        int cur = dpd[u][max(dis[from][v] - 1, 0)];
        if (cur > dp[u][from]) cur = dp[u][from];
        dp[v][from] += cur;
      }
    }
    int len = dis[v][from];
    if (isPar(v, from) && dpd[v][len] > dp[v][from]) {
      dpd[v][len] = dp[v][from];
      ans[v][len] = from;
    }
  }
  for (int i = n - 2; i >= 0; i--)
    if (dpd[v][i] > dpd[v][i + 1]) {
      dpd[v][i] = dpd[v][i + 1];
      ans[v][i] = ans[v][i + 1];
    }
}
void solve(int v, int par, int from) {
  out[v] = from;
  for (auto u : g[v]) {
    if (u == par) continue;
    if (isPar(u, from))
      solve(u, v, from);
    else {
      int len = max(0, dis[v][from] - 1);
      solve(u, v, (dpd[u][len] <= dp[u][from] ? ans[u][len] : from));
    }
  }
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n - 1; i++) cin >> d[i];
  d[0] = k;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 0; i < n; i++) dfs_dis(i, i);
  dfs_prep();
  dfs();
  cout << dpd[0][0] << "\n";
  solve(0, -1, ans[0][0]);
  for (int i = 0; i < n; i++) cout << out[i] + 1 << " \n"[i == n - 1];
}
