#include <bits/stdc++.h>
using namespace std;
const int N = 200;
struct Edge {
  int nxt, to;
  Edge(int nxt = 0, int to = 0) : nxt(nxt), to(to) {}
} e[N << 1];
int first[N], cur;
void connect(int x, int y) {
  e[++cur] = Edge(first[x], y);
  first[x] = cur;
}
int n, k;
int d[N];
int dis[N][N];
int f[N][N], p[N];
void dfs(int x, int fa, int y) {
  if (fa != x) dis[y][x] = dis[y][fa] + 1;
  for (int i = first[x]; i; i = e[i].nxt)
    if (e[i].to != fa) dfs(e[i].to, x, y);
}
void get(int x, int fa) {
  for (int i = 1; i <= n; i++) f[x][i] = d[dis[x][i]] + k;
  for (int i = first[x]; i; i = e[i].nxt)
    if (e[i].to != fa) {
      get(e[i].to, x);
      for (int j = 1; j <= n; j++)
        f[x][j] += min(f[e[i].to][p[e[i].to]], f[e[i].to][j] - k);
    }
  p[x] = 1;
  for (int i = 1; i <= n; i++)
    if (f[x][i] < f[x][p[x]]) p[x] = i;
}
int ans[N];
void get_ans(int x, int fa, int pos) {
  ans[x] = pos;
  for (int i = first[x]; i; i = e[i].nxt)
    if (e[i].to != fa)
      get_ans(e[i].to, x,
              f[e[i].to][p[e[i].to]] < f[e[i].to][pos] - k ? p[e[i].to] : pos);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> k;
  for (int i = 1; i < n; i++) cin >> d[i];
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    connect(u, v), connect(v, u);
  }
  for (int i = 1; i <= n; i++) dis[i][i] = 0, dfs(i, i, i);
  get(1, 0), get_ans(1, 0, p[1]);
  cout << f[1][p[1]] << endl;
  for (int i = 1; i <= n; i++) cout << ans[i] << " ";
  cout << endl;
  return 0;
}
