#include <bits/stdc++.h>
using namespace std;
const int maxn = 180 + 10;
const int oo = 1000000000;
int opt[maxn][maxn * 2];
int c[maxn][maxn * 2], cc[maxn][maxn * 2];
int e[maxn][maxn];
int n, kk, d[maxn];
int father[maxn];
int res[maxn];
void dp(int u) {
  for (int v = 1; v <= n; v++)
    if (e[u][v] && v == father[u]) e[u][v] = 0;
  for (int v = 1; v <= n; v++)
    if (e[u][v]) {
      father[v] = u;
      dp(v);
    }
  for (int i = 1; i <= n; i++) {
    int w = i - n, o = 0;
    for (int v = 1; v <= n; v++)
      if (e[u][v]) {
        int o2 = opt[v][i - 1];
        for (int j = n; j <= n * 2; j++) o2 = min(o2, opt[v][j]);
        o += o2;
        o = min(o, oo);
      }
    if (w == 0)
      o += kk;
    else
      o += d[-w];
    opt[u][i] = o;
  }
  int best[maxn];
  for (int i = n + 1; i < n * 2; i++) {
    for (int v = 1; v <= n; v++)
      if (e[u][v]) {
        best[v] = oo;
        for (int j = i - 1; j <= n * 2; j++) best[v] = min(best[v], opt[v][j]);
        best[v] = min(best[v], opt[v][n + n - i - 1]);
      }
    for (int v = 1; v <= n; v++)
      if (e[u][v]) {
        int o = opt[v][i - 1];
        for (int w = 1; w <= n; w++)
          if (w != v && e[u][w]) {
            o += best[w];
            o = min(o, oo);
          }
        o += d[i - n];
        if (o < opt[u][i]) {
          opt[u][i] = o;
          cc[u][i] = v;
        }
      }
  }
}
void dfs(int u, int w, int p) {
  if (w == n) p = u;
  if (w <= n) {
    res[u] = p;
    for (int v = 1; v <= n; v++)
      if (e[u][v]) {
        int o = w - 1;
        for (int j = n; j <= n * 2; j++)
          if (opt[v][j] < opt[v][o]) o = j;
        dfs(v, o, p);
      }
  } else {
    int o = cc[u][w];
    dfs(o, w - 1, p);
    res[u] = res[o];
    for (int v = 1; v <= n; v++)
      if (v != o && e[u][v]) {
        int _o = n + n - w - 1;
        for (int j = w - 1; j <= n * 2; j++)
          if (opt[v][j] < opt[v][_o]) _o = j;
        dfs(v, _o, res[u]);
      }
  }
}
int main() {
  scanf("%d%d", &n, &kk);
  for (int i = 1; i < n; i++) scanf("%d", &d[i]);
  for (int i = 1, u, v; i < n; i++) {
    scanf("%d%d", &u, &v);
    e[u][v] = e[v][u] = 1;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= n * 2 + 1; j++) opt[i][j] = oo;
  dp(1);
  int best = n;
  for (int i = n; i <= n * 2; i++)
    if (opt[1][i] < opt[1][best]) best = i;
  dfs(1, best, 0);
  printf("%d\n", opt[1][best]);
  for (int i = 1; i <= n; i++) printf("%d%c", res[i], i == n ? '\n' : ' ');
}
