#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int n, t, d[190], dp[190][190], dist[190][190], best[190], ans[190];
vector<int> g[190];
void dfs(int pos, int par) {
  for (int i = 0; i < g[pos].size(); ++i)
    if (g[pos][i] != par) dfs(g[pos][i], pos);
  int mn = 1e9;
  for (int i = 1; i <= n; ++i) {
    dp[pos][i] = d[dist[pos][i]];
    for (int j = 0; j < g[pos].size(); ++j)
      if (g[pos][j] != par)
        dp[pos][i] += min(dp[g[pos][j]][i], dp[g[pos][j]][best[g[pos][j]]] + t);
    if (dp[pos][i] < mn) {
      mn = dp[pos][i];
      best[pos] = i;
    }
  }
}
void getAns(int pos, int to, int par) {
  ans[pos] = to;
  for (int i = 0; i < g[pos].size(); ++i)
    if (g[pos][i] != par) {
      if (dp[g[pos][i]][to] < dp[g[pos][i]][best[g[pos][i]]] + t)
        getAns(g[pos][i], to, pos);
      else
        getAns(g[pos][i], best[g[pos][i]], pos);
    }
}
int main() {
  cin >> n >> t;
  for (int i = 0; i < n + 5; ++i)
    for (int j = 0; j < n + 5; ++j)
      if (i != j) dist[i][j] = 1e9;
  for (int i = 1; i <= n - 1; ++i) scanf("%d", &d[i]);
  int x, y;
  for (int i = 0; i < n - 1; ++i) {
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
    dist[x][y] = dist[y][x] = 1;
  }
  for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);
  dfs(1, 0);
  cout << dp[1][best[1]] + t << endl;
  getAns(1, best[1], 0);
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  cout << endl;
  return 0;
}
