#include <bits/stdc++.h>
using namespace std;
int N, K, A, B;
int D[191];
vector<int> G[181];
int d[180][180];
int par[180];
int best[180];
bitset<180> bb[180];
bitset<180> cb[180];
bitset<180> df[180][180];
bitset<180> cf[180][180];
int dp[180][180];
void solve(int v, int c, int p) {
  dp[v][c] = d[v][c];
  cf[v][c].set(c);
  for (int(i) = 0; (i) < (G[v].size()); (i)++)
    if (G[v][i] != p) {
      int u = G[v][i];
      if (dp[u][c] > best[u]) {
        dp[v][c] += best[u];
        df[v][c] = df[v][c] | bb[u];
        cf[v][c] = cf[v][c] | cb[u];
      } else {
        dp[v][c] += dp[u][c];
        df[v][c] = df[v][c] | df[u][c];
        df[v][c].set(u);
        cf[v][c] = cf[v][c] | cf[u][c];
      }
    }
}
void dfs(int v, int p) {
  par[v] = p;
  for (int(i) = 0; (i) < (G[v].size()); (i)++)
    if (G[v][i] != p) dfs(G[v][i], v);
  for (int(i) = 0; (i) < (N); (i)++) solve(v, i, p);
  int pos = 0;
  for (int(i) = (1); (i) < (N); (i)++)
    if (dp[v][i] < dp[v][pos]) pos = i;
  best[v] = dp[v][pos] + K;
  bb[v] = df[v][pos];
  cb[v] = cf[v][pos];
}
struct UnionFind {
  int par[180], ans[180];
  UnionFind() {
    for (int(i) = 0; (i) < (180); (i)++) par[i] = i;
  }
  int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
  void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    par[b] = a;
  }
} uf;
int main() {
  scanf("%d%d", &N, &K);
  for (int(i) = 0; (i) < (N - 1); (i)++) scanf("%d", &D[i + 1]);
  for (int(i) = 0; (i) < (N); (i)++)
    for (int(j) = 0; (j) < (N); (j)++) d[i][j] = (1 << 29) * (i != j);
  for (int(i) = 0; (i) < (N - 1); (i)++) {
    scanf("%d%d", &A, &B);
    A--, B--;
    G[A].push_back(B);
    G[B].push_back(A);
    d[A][B] = d[B][A] = 1;
  }
  for (int(k) = 0; (k) < (N); (k)++)
    for (int(i) = 0; (i) < (N); (i)++)
      for (int(j) = 0; (j) < (N); (j)++)
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  for (int(i) = 0; (i) < (N); (i)++)
    for (int(j) = 0; (j) < (N); (j)++) d[i][j] = D[d[i][j]];
  dfs(0, -1);
  printf("%d\n", best[0]);
  for (int(i) = (1); (i) < (N); (i)++)
    if (bb[0].test(i)) uf.unite(i, par[i]);
  for (int(i) = 0; (i) < (N); (i)++)
    if (cb[0].test(i)) uf.ans[uf.find(i)] = i + 1;
  for (int(i) = 0; (i) < (N); (i)++)
    printf("%d%c", uf.ans[uf.find(i)], i + 1 == N ? '\n' : ' ');
}
