#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 mp[Max][Max];
int F[Max][Max];
int A[Max], R[Max];
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 f) {
  for (edge *p = hd[x]; p; p = p->s)
    if (p->to != f) dfs(p->to, x);
  for (int i = 1; i <= n; i++) {
    int &cr = F[x][i] = 0;
    int dx = mp[x][i];
    for (edge *p = hd[x]; p; p = p->s)
      if (p->to != f) {
        int y = p->to;
        cr += dx < mp[y][i] ? min(R[y], F[y][i]) : F[y][i];
      }
    cr += D[dx];
    if (x == i) cr += k;
    if (dx < mp[f][i]) update(R[x], cr);
  }
}
void aDfs(int x, int f, int g) {
  if (g == 0) {
    for (int i = 1; i <= n; i++)
      if (mp[x][i] < mp[f][i] && F[x][i] == R[x]) {
        aDfs(x, f, i);
        return;
      }
  }
  A[x] = g;
  for (edge *p = hd[x]; p; p = p->s)
    if (p->to != f) {
      int y = p->to;
      aDfs(y, x, mp[x][g] < mp[y][g] && R[y] < F[y][g] ? 0 : g);
    }
}
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, 0, sizeof(hd));
    memset(mp, 0x3f, sizeof(mp));
    cp = E;
    for (int i = 1; i < n; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      mp[x][y] = mp[y][x] = 1;
      addEdge(x, y);
      addEdge(y, x);
    }
    for (int z = 1; z <= n; z++)
      for (int x = 1; x <= n; x++)
        for (int y = 1; y <= n; y++) update(mp[x][y], mp[x][z] + mp[z][y]);
    for (int x = 1; x <= n; x++) mp[x][x] = 0;
    memset(R, 0x3f, sizeof(R));
    dfs(1, 0);
    printf("%d\n", R[1]);
    aDfs(1, 0, 0);
    for (int i = 1; i <= n; i++) printf("%d%c", A[i], i == n ? '\n' : ' ');
  }
}
