#include <bits/stdc++.h>
using namespace std;
int n, K, d[205], f[205][205][205], g[205][205], pa[205], dis[205][205];
struct node {
  int i, j, k;
  node() {}
  node(int a, int b, int c) {
    i = a;
    j = b;
    k = c;
  }
};
node ffrom[205][205][205], gfrom[205][205];
vector<int> e[205], vec;
void dfs1(int rt, int u, int fa) {
  dis[rt][u] = dis[rt][fa] + 1;
  for (auto v : e[u])
    if (v != fa) {
      dfs1(rt, v, u);
    }
}
void dfs(int u, int fa) {
  bool flag = 0;
  pa[u] = fa;
  for (auto v : e[u])
    if (v != fa) {
      dfs(v, u);
      flag = 1;
    }
  if (flag == 0) {
    for (int j = (1); j <= (n); j++) {
      f[u][j][0] = K;
      ffrom[u][j][0] = node(-1, -1, -1);
      f[u][j][n] = d[j];
      ffrom[u][j][n] = node(0, 0, 0);
      if (f[u][j][0] < g[u][j])
        g[u][j] = f[u][j][0], gfrom[u][j] = node(u, j, 0);
      if (f[u][j][n] < g[u][j])
        g[u][j] = f[u][j][n], gfrom[u][j] = node(u, j, n);
    }
    return;
  }
  for (int j = (1); j <= (n); j++)
    for (int k = (0); k <= (n); k++) {
      long long sum = 0;
      int Min = 0x3f3f3f3f;
      if (k == 0) {
        for (auto v : e[u])
          if (v != fa) {
            sum += g[v][1];
          }
        if (sum + K < f[u][j][k])
          f[u][j][k] = sum + K, ffrom[u][j][k] = node(-1, -1, -1);
        if (f[u][j][k] < 0x3f3f3f3f) {
        }
        if (f[u][j][k] < g[u][j])
          g[u][j] = f[u][j][k], gfrom[u][j] = node(u, j, k);
        continue;
      }
      if (k == n) {
        node from = node(0, 0, 0);
        for (auto v : e[u])
          if (v != fa) {
            sum += f[v][j + 1][k];
          }
        if (sum + d[j] < f[u][j][k])
          f[u][j][k] = sum + d[j], ffrom[u][j][k] = from;
        if (f[u][j][k] < 0x3f3f3f3f) {
        }
        if (f[u][j][k] < g[u][j])
          g[u][j] = f[u][j][k], gfrom[u][j] = node(u, j, k);
        continue;
      }
      node from;
      for (auto v : e[u])
        if (v != fa) {
          sum += g[v][min(min(j, k) + 1, n)];
          if (f[v][min(j + 1, n)][k - 1] - g[v][min(min(j, k) + 1, n)] < Min) {
            Min = f[v][min(j + 1, n)][k - 1] - g[v][min(min(j, k) + 1, n)];
            from = node(v, min(j + 1, n), k - 1);
          }
        }
      if (sum + Min + d[min(j, k)] < f[u][j][k])
        f[u][j][k] = sum + Min + d[min(j, k)], ffrom[u][j][k] = from;
      if (f[u][j][k] < 0x3f3f3f3f) {
      }
      if (f[u][j][k] < g[u][j])
        g[u][j] = f[u][j][k], gfrom[u][j] = node(u, j, k);
    }
}
void tag(node cur) {
  if (ffrom[cur.i][cur.j][cur.k].i == 0) return;
  if (ffrom[cur.i][cur.j][cur.k].i == -1) {
    vec.push_back(cur.i);
    for (auto v : e[cur.i])
      if (v != pa[cur.i]) {
        tag(gfrom[v][1]);
      }
    return;
  }
  tag(ffrom[cur.i][cur.j][cur.k]);
  for (auto v : e[cur.i])
    if (v != pa[cur.i] && v != ffrom[cur.i][cur.j][cur.k].i) {
      tag(gfrom[v][min(min(cur.j, cur.k) + 1, n)]);
    }
}
int main() {
  scanf("%d%d", &n, &K);
  for (int i = (1); i <= (n); i++)
    for (int j = (1); j <= (n); j++)
      for (int k = (0); k <= (n); k++) f[i][j][k] = g[i][j] = 0x3f3f3f3f;
  for (int i = (1); i <= (n - 1); i++) scanf("%d", &d[i]);
  d[n] = 0x3f3f3f3f;
  for (int i = (2); i <= (n); i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(1, 0);
  int ans = 0x3f3f3f3f;
  node from;
  for (int i = (0); i <= (n - 1); i++)
    if (f[1][n][i] < ans) ans = f[1][n][i], from = node(1, n, i);
  printf("%d\n", ans);
  tag(from);
  for (int i = (1); i <= (n); i++) dfs1(i, i, 0);
  for (int i = (1); i <= (n); i++) {
    int cur = vec[0];
    for (auto v : vec)
      if (dis[i][v] < dis[i][cur]) cur = v;
    printf("%d ", cur);
  }
  return 0;
}
