#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void gmin(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
void PV(T x) {
  for (__typeof__((x).begin()) i = (x).begin(); i != (x).end(); i++)
    cout << *i << " ";
  cout << endl;
}
template <class T>
void PA(T x[], int n) {
  for (int i = 0; i < n; i++) cout << x[i] << " ";
  cout << endl;
}
const int N = 180;
vector<int> lnk[N], d;
int n, m;
int p[N][N];
void calc_p(int root, int dep, int now, int fth) {
  p[root][now] = d[dep];
  for (__typeof__(lnk[now].begin()) _it = lnk[now].begin();
       _it != lnk[now].end(); ++_it)
    for (int _once = 1, _done = 0; _once;
         (!_done) ? (_it = lnk[now].end(), --_it) : _it)
      for (__typeof__(*_it) &next = *_it; _once && !(_once = 0); _done = 1)
        if (next != fth) calc_p(root, dep + 1, next, now);
}
int f[N][N], f2[N];
void dp(int now, int fth) {
  for (__typeof__(lnk[now].begin()) _it = lnk[now].begin();
       _it != lnk[now].end(); ++_it)
    for (int _once = 1, _done = 0; _once;
         (!_done) ? (_it = lnk[now].end(), --_it) : _it)
      for (__typeof__(*_it) &next = *_it; _once && !(_once = 0); _done = 1)
        if (next != fth) dp(next, now);
  for (int n_ = (n), c = 0; c < n_; ++c) f[now][c] = p[now][c] + m;
  for (int n_ = (n), c = 0; c < n_; ++c)
    for (__typeof__(lnk[now].begin()) _it = lnk[now].begin();
         _it != lnk[now].end(); ++_it)
      for (int _once = 1, _done = 0; _once;
           (!_done) ? (_it = lnk[now].end(), --_it) : _it)
        for (__typeof__(*_it) &next = *_it; _once && !(_once = 0); _done = 1)
          if (next != fth) f[now][c] += min(f[next][c] - m, f[next][f2[next]]);
  f2[now] = 0;
  for (int n_ = (n), c = 0; c < n_; ++c)
    if (f[now][c] < f[now][f2[now]]) f2[now] = c;
}
vector<int> ans;
void dp2(int now, int fth, int c) {
  ans[now] = c + 1;
  for (__typeof__(lnk[now].begin()) _it = lnk[now].begin();
       _it != lnk[now].end(); ++_it)
    for (int _once = 1, _done = 0; _once;
         (!_done) ? (_it = lnk[now].end(), --_it) : _it)
      for (__typeof__(*_it) &next = *_it; _once && !(_once = 0); _done = 1)
        if (next != fth) {
          if (f[next][c] - m < f[next][f2[next]])
            dp2(next, now, c);
          else
            dp2(next, now, f2[next]);
        }
}
void work() {
  for (int n_ = (n), i = 0; i < n_; ++i) calc_p(i, 0, i, -1);
  dp(0, -1);
  ans.resize(n);
  dp2(0, -1, f2[0]);
  cout << f[0][f2[0]] << endl;
  PV(ans);
}
void myin() {
  cin >> n >> m;
  d.assign(n, 0);
  for (int n_ = (n - 1), i = 0; i < n_; ++i) cin >> d[i + 1];
  for (int n_ = (n), i = 0; i < n_; ++i) lnk[i].clear();
  for (int n_ = (n - 1), i = 0; i < n_; ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    lnk[u].push_back(v);
    lnk[v].push_back(u);
  }
}
int main() {
  myin();
  work();
  return 0;
}
