#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
const int Max = 256;
const int MaxE = Max * 2;
struct edge {
  int to;
  edge *s;
};
edge E[MaxE], *hd[Max], *cp;
int n, k, D[Max];
int F[Max][Max];
int G[Max][Max];
int R[Max], A[Max];
int Q[Max], qn;
void addEdge(int x, int y) { cp->to = y, cp->s = hd[x], hd[x] = cp++; }
inline void update(int &r, int d) {
  if (d < r) r = d;
}
void dfs(int x, int pf) {
  int sn = 0;
  for (edge *p = hd[x]; p; p = p->s)
    if (p->to != pf) {
      dfs(p->to, x);
      ++sn;
    }
  G[x][0] = k;
  for (edge *p = hd[x]; p; p = p->s)
    if (p->to != pf) G[x][0] += min(R[p->to], F[p->to][1]);
  for (int i = 0; i + 1 < n; i++) {
    if (sn == 0) break;
    int cs = 0;
    for (edge *p = hd[x]; p; p = p->s)
      if (p->to != pf) cs += min(R[p->to], F[p->to][i + 2]);
    int &cr = G[x][i + 1];
    for (edge *p = hd[x]; p; p = p->s)
      if (p->to != pf) {
        int d = min(R[p->to], F[p->to][i + 2]);
        update(cr, cs - d + G[p->to][i]);
      }
    cr += D[i + 1];
  }
  R[x] = oo;
  for (int i = 0; i < n; i++) update(R[x], G[x][i]);
  for (int i = 1; i + 1 < n; i++) {
    int &cr = F[x][i] = D[i];
    for (edge *p = hd[x]; p; p = p->s)
      if (p->to != pf) cr += min(R[p->to], F[p->to][i + 1]);
  }
}
void aDfs(int x, int pf, int c, int e) {
  if (c == 0) {
    int ri = -1;
    for (int i = 0; i < n; i++)
      if (R[x] == G[x][i]) {
        ri = i;
        break;
      }
    aDfs(x, pf, 2, ri);
  } else if (c == 1) {
    for (edge *p = hd[x]; p; p = p->s)
      if (p->to != pf) {
        if (R[p->to] < F[p->to][e + 1])
          aDfs(p->to, x, 0, 0);
        else
          aDfs(p->to, x, 1, e + 1);
      }
  } else if (c == 2) {
    if (e == 0) {
      A[x] = x;
      Q[qn++] = x;
      for (edge *p = hd[x]; p; p = p->s)
        if (p->to != pf) {
          if (R[p->to] < F[p->to][1])
            aDfs(p->to, x, 0, 0);
          else
            aDfs(p->to, x, 1, 1);
        }
      return;
    }
    int cs = 0;
    for (edge *p = hd[x]; p; p = p->s)
      if (p->to != pf) cs += min(R[p->to], F[p->to][e + 1]);
    for (edge *p = hd[x]; p; p = p->s)
      if (p->to != pf) {
        int d = min(R[p->to], F[p->to][e + 1]);
        if (G[x][e] == cs - d + G[p->to][e - 1] + D[e]) {
          int y = p->to;
          aDfs(y, x, 2, e - 1);
          for (edge *p = hd[x]; p; p = p->s)
            if (p->to != pf && p->to != y) {
              if (R[p->to] < F[p->to][e + 1])
                aDfs(p->to, x, 0, 0);
              else
                aDfs(p->to, x, 1, e + 1);
            }
          break;
        }
      }
  }
}
int main() {
  while (scanf("%d%d", &n, &k) != EOF && n) {
    for (int i = 1; i < n; i++) scanf("%d", &D[i]);
    D[n] = oo;
    memset(hd + 1, 0, sizeof(hd[0]) * n);
    cp = E;
    for (int i = 1; i < n; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      addEdge(x, y);
      addEdge(y, x);
    }
    memset(F, 0x3f, sizeof(F));
    memset(G, 0x3f, sizeof(G));
    dfs(1, -1);
    printf("%d\n", R[1]);
    memset(A, -1, sizeof(A));
    qn = 0;
    aDfs(1, -1, 0, 0);
    for (int cq = 0; cq < qn; cq++) {
      int x = Q[cq];
      for (edge *p = hd[x]; p; p = p->s)
        if (A[p->to] == -1) {
          A[p->to] = A[x];
          Q[qn++] = p->to;
        }
    }
    for (int i = 1; i <= n; i++) printf("%d%c", A[i], i == n ? '\n' : ' ');
  }
}
