#include <bits/stdc++.h>
using namespace std;
int n, m;
int d[200], f[200][200];
int c[200];
int dis[200][200];
long long fa[200];
int ans[200];
void floyed() {
  for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
void dfs_1(int x) {
  for (int i = 1; i <= n; ++i) f[x][i] = d[dis[x][i]] + m;
  for (int i = 1; i <= n; ++i) {
    if (dis[x][i] == 1 && (fa[x] != i)) {
      fa[i] = x;
      dfs_1(i);
      for (int j = 1; j <= n; ++j) f[x][j] += min(f[i][j] - m, f[i][c[i]]);
    }
  }
  c[x] = 1;
  for (int i = 1; i <= n; ++i)
    if (f[x][c[x]] > f[x][i]) c[x] = i;
}
void dfs_2(int x, int y) {
  ans[x] = y;
  for (int i = 1; i <= n; ++i) {
    if (dis[i][x] == 1 && (fa[i] == x)) {
      if (f[i][y] - m >= f[i][c[i]])
        dfs_2(i, c[i]);
      else
        dfs_2(i, y);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n - 1; ++i) scanf("%d", &d[i]);
  memset(dis, 53, sizeof(dis));
  for (int i = 1; i <= n - 1; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    dis[x][y] = 1;
    dis[y][x] = 1;
  }
  for (int i = 1; i <= n; ++i) dis[i][i] = 0;
  floyed();
  dfs_1(1);
  cout << f[1][c[1]] << endl;
  dfs_2(1, c[1]);
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  return 0;
}
