#include <bits/stdc++.h>
using namespace std;
int a, b, c, d, e, f, g, h, i, j, k;
int F[205][205];
int G[205];
int num[205];
int father[205];
int L[205];
int D[205][205];
vector<int> GG[205];
int an;
int belong[205];
void soso(int x) {
  int ii, jj, kk;
  for (ii = 0; ii < GG[x].size(); ii++) {
    jj = GG[x][ii];
    if (jj == father[x]) continue;
    father[jj] = x;
    soso(jj);
  }
  for (ii = 1; ii <= a; ii++) {
    F[x][ii] = b + L[D[x][ii]];
    for (jj = 0; jj < GG[x].size(); jj++) {
      kk = GG[x][jj];
      if (kk == father[x]) continue;
      F[x][ii] += min(F[kk][ii] - b, G[kk]);
    }
  }
  G[x] = 1 << 30;
  for (ii = 1; ii <= a; ii++) {
    if (F[x][ii] < G[x]) {
      G[x] = F[x][ii];
      num[x] = ii;
    }
  }
}
void Get_Belong(int x, int y) {
  int ii, jj, kk;
  belong[x] = y;
  for (ii = 0; ii < GG[x].size(); ii++) {
    jj = GG[x][ii];
    if (jj == father[x]) continue;
    if (F[jj][y] - b < G[jj])
      Get_Belong(jj, y);
    else
      Get_Belong(jj, num[jj]);
  }
}
int main() {
  cin >> a >> b;
  for (i = 1; i < a; i++) cin >> L[i];
  for (i = 1; i <= a; i++)
    for (j = 1; j <= a; j++)
      if (i != j) D[i][j] = 1 << 29;
  for (i = 1; i < a; i++) {
    cin >> c >> d;
    GG[c].push_back(d);
    GG[d].push_back(c);
    D[c][d] = D[d][c] = 1;
  }
  for (k = 1; k <= a; k++)
    for (i = 1; i <= a; i++)
      for (j = 1; j <= a; j++) D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
  soso(1);
  cout << G[1] << endl;
  Get_Belong(1, num[1]);
  for (i = 1; i <= a; i++) cout << belong[i] << " ";
  cout << endl;
  return 0;
}
