#include <bits/stdc++.h>
using namespace std;
long long n, wv, d[200], dist[200][200], dp[200][200], par[200], best[200],
    trace[200][200], ans[200];
vector<vector<long long> > gr(200);
void dfs(long long u) {
  for (long long i = 0; i < gr[u].size(); ++i) {
    long long v = gr[u][i];
    if (v != par[u]) {
      par[v] = u;
      dfs(v);
    }
  }
}
void dpp(long long u) {
  long long currc = 1e18;
  for (long long i = 1; i <= n; ++i) {
    for (long long j = 0; j < gr[u].size(); ++j) {
      long long v = gr[u][j];
      if (v != par[u]) {
        if (i == 1) dpp(v);
        if (dp[v][i] - wv < dp[v][best[v]]) {
          dp[u][i] += dp[v][i] - wv;
          trace[v][i] = i;
        } else {
          dp[u][i] += dp[v][best[v]];
          trace[v][i] = best[v];
        }
      }
    }
    dp[u][i] += wv + d[dist[u][i]];
    if (dp[u][i] < currc) {
      currc = dp[u][i];
      best[u] = i;
    }
  }
}
void tracee(long long now1, long long now2) {
  for (long long i = 0; i < gr[now1].size(); ++i) {
    long long v = gr[now1][i];
    if (v != par[now1]) {
      ans[v] = trace[v][now2];
      tracee(v, ans[v]);
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> wv;
  for (long long i = 1; i < n; ++i) cin >> d[i];
  memset(dist, 1, sizeof dist);
  for (long long i = 1; i < n; ++i) {
    long long x, y;
    cin >> x >> y;
    gr[x].push_back(y);
    gr[y].push_back(x);
    dist[x][y] = dist[y][x] = 1;
  }
  dfs(1);
  for (long long i = 1; i <= n; ++i) dist[i][i] = 0;
  for (long long k = 1; k <= n; ++k) {
    for (long long i = 1; i <= n; ++i) {
      for (long long j = 1; j <= n; ++j) {
        dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);
      }
    }
  }
  dpp(1);
  cout << dp[1][best[1]] << "\n";
  ans[1] = best[1];
  long long now1 = 1, now2 = best[1];
  tracee(now1, now2);
  for (long long i = 1; i <= n; ++i) cout << ans[i] << " ";
  return 0;
}
