#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, mod = 1000000007;
const double pi = 3.1415926535897932, eps = 1e-6;
void chmax(int &x, int y) {
  if (x < y) x = y;
}
void chmin(int &x, int y) {
  if (x > y) x = y;
}
int n, k, d[205];
int dp[205][205], dis[205][205], opt[205], way[205];
bool p[205];
vector<int> v[205];
void dfs(int x, int fa) {
  if (p[x]) return;
  p[x] = 1;
  for (int(j) = (0); (j) < (v[x].size()); (j)++) {
    int to = v[x][j];
    if (to == fa) continue;
    dfs(to, x);
  }
  for (int(i) = (1); (i) <= (n); (i)++) {
    dp[x][i] = d[dis[x][i]] + k;
    for (int(j) = (0); (j) < (v[x].size()); (j)++) {
      int to = v[x][j];
      if (to == fa) continue;
      int cost1 = dp[to][i] - k;
      int cost2 = dp[to][opt[to]];
      dp[x][i] += min(cost1, cost2);
    }
    if (opt[x] == 0 || dp[x][i] < dp[x][opt[x]]) opt[x] = i;
  }
}
void rec(int x, int nxt, int fa) {
  way[x] = nxt;
  for (int(j) = (0); (j) < (v[x].size()); (j)++) {
    int to = v[x][j];
    if (to == fa) continue;
    int cost1 = dp[to][nxt] - k;
    int cost2 = dp[to][opt[to]];
    if (cost1 < cost2)
      rec(to, nxt, x);
    else
      rec(to, opt[to], x);
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int(i) = (1); (i) <= (n - 1); (i)++) scanf("%d", d + i);
  for (int(i) = (1); (i) <= (n); (i)++)
    for (int(j) = (1); (j) <= (n); (j)++)
      if (i != j) dis[i][j] = inf;
  for (int(i) = (1); (i) < (n); (i)++) {
    int t1, t2;
    scanf("%d%d", &t1, &t2);
    v[t1].push_back(t2);
    v[t2].push_back(t1);
    dis[t1][t2] = dis[t2][t1] = 1;
  }
  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]);
  dfs(1, 0);
  int ans = dp[1][opt[1]];
  printf("%d\n", ans);
  rec(1, opt[1], 0);
  for (int(i) = (1); (i) <= (n); (i)++) printf("%d ", way[i]);
  return 0;
}
