#include <bits/stdc++.h>
using namespace std;
const int MAXN = 180 + 10;
int N, K, dis[MAXN][MAXN], d[MAXN], f[MAXN][MAXN], rec[MAXN][MAXN][MAXN];
vector<int> E[MAXN];
void dfs(int u, int fr) {
  for (int RC = (0), RCend = (N); RC < RCend; ++RC) f[u][RC] = d[dis[u][RC]];
  for (int v : E[u])
    if (v != fr) {
      dfs(v, u);
      for (int RC = (0), RCend = (N); RC < RCend; ++RC) {
        int mn = INT_MAX;
        for (int RCv = (0), RCvend = (N); RCv < RCvend; ++RCv) {
          if (RCv != RC) {
            if (mn > f[v][RCv] + K) mn = f[v][RCv] + K, rec[u][RC][v] = RCv;
          } else {
            if (mn > f[v][RC]) mn = f[v][RC], rec[u][RC][v] = RC;
          }
        }
        f[u][RC] += mn;
      }
    }
}
int fans[MAXN];
void recover(int u, int RC, int fr) {
  fans[u] = RC;
  for (int v : E[u])
    if (v != fr) recover(v, rec[u][RC][v], u);
}
int main() {
  scanf("%d %d", &N, &K);
  for (int i = (1), iend = (N); i < iend; ++i) scanf("%d", &d[i]);
  memset(dis, 0x3f, sizeof dis);
  for (int i = (0), iend = (N); i < iend; ++i) dis[i][i] = 0;
  for (int i = (0), iend = (N - 1); i < iend; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    u--, v--;
    dis[u][v] = dis[v][u] = 1;
    E[u].push_back(v), E[v].push_back(u);
  }
  for (int k = (0), kend = (N); k < kend; ++k)
    for (int i = (0), iend = (N); i < iend; ++i)
      for (int j = (0), jend = (N); j < jend; ++j)
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  dfs(0, -1);
  int ans = INT_MAX, RC0;
  for (int RC = (0), RCend = (N); RC < RCend; ++RC) {
    if (ans > f[0][RC] + K) ans = f[0][RC] + K, RC0 = RC;
  }
  printf("%d\n", ans);
  recover(0, RC0, -1);
  for (int i = (0), iend = (N); i < iend; ++i) printf("%d ", fans[i] + 1);
  return 0;
}
