#include <bits/stdc++.h>
using namespace std;
vector<int> v[188];
int dist[188][188];
int n, m;
int dp[188][188];
int best[188];
void dfs(int x, int p) {
  for (int i = 0; i < v[x].size(); i++) {
    int t = v[x][i];
    if (t != p) dfs(t, x);
  }
  best[x] = 1;
  for (int c = 1; c <= n; c++) {
    for (int j = 0; j < v[x].size(); j++) {
      int t = v[x][j];
      if (t == p) continue;
      dp[x][c] += min(dp[t][c], dp[t][best[t]] + m);
    }
    dp[x][c] += dist[x][c];
    if (dp[x][c] < dp[x][best[x]]) best[x] = c;
  }
}
int bel[188];
void process(int x, int p, int c) {
  bel[x] = c;
  for (int i = 0; i < v[x].size(); i++) {
    int t = v[x][i];
    if (t == p) continue;
    if (dp[t][c] < dp[t][best[t]] + m)
      process(t, x, c);
    else
      process(t, x, best[t]);
  }
}
int cost[188];
int main() {
  cin >> n >> m;
  memset(dist, 0x3f, sizeof(dist));
  for (int i = 1; i < n; i++) cin >> cost[i];
  dist[1][1] = 0;
  for (int i = 1; i < n; i++) {
    dist[i + 1][i + 1] = 0;
    int x, y;
    scanf("%d%d", &x, &y);
    dist[x][y] = dist[y][x] = 1;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      for (int k = 1; k <= n; k++)
        dist[j][k] = min(dist[j][i] + dist[i][k], dist[j][k]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) dist[i][j] = cost[dist[i][j]];
  dfs(1, 0);
  cout << dp[1][best[1]] + m << "\n";
  process(1, 0, best[1]);
  for (int i = 1; i <= n; i++) cout << bel[i] << " ";
  return 0;
}
