#include <bits/stdc++.h>
using namespace std;
const int N = 120 + 77;
const int inf = 1000000000 + 77;
int n, k, C[N], A[N];
int dp[N][N][2];
int Par[N][N][2];
vector<int> adj[N];
void dfs(int v, int prev = -1) {
  vector<int> Ch;
  for (int u : adj[v])
    if (u != prev) dfs(u, v), Ch.push_back(u);
  dp[v][0][1] = k;
  for (int u : Ch) dp[v][0][1] += min(dp[u][0][1], dp[u][1][1]);
  dp[v][0][0] = dp[v][0][1];
  for (int i = 1; i < n; ++i) {
    dp[v][i][1] = C[i];
    int tot = 0;
    bool good = 1, ff = 1;
    for (int u : Ch) {
      dp[v][i][1] += min(min(dp[u][i + 1][1], dp[u][i][0]), dp[u][i - 1][0]),
          tot += min(min(dp[u][i - 1][0], dp[u][i][0]), dp[u][i + 1][1]);
      if (min(min(dp[u][i - 1][0], dp[u][i][0]), dp[u][i + 1][1]) > 1e8)
        good = 0;
      if (min(min(dp[u][i + 1][1], dp[u][i][0]), dp[u][i - 1][0]) > 1e8) ff = 0;
    }
    if (!ff) dp[v][i][1] = inf;
    if (!good) continue;
    for (int u : Ch) {
      int val = dp[u][i - 1][0] + tot -
                min(min(dp[u][i - 1][0], dp[u][i][0]), dp[u][i + 1][1]);
      if (val < dp[v][i][0]) Par[v][i][0] = u, dp[v][i][0] = val;
    }
    dp[v][i][0] += C[i];
  }
}
void Solve(int v, int d, int t, int prev = -1) {
  if (d == 0)
    A[v] = v;
  else if (t == 1)
    A[v] = A[prev];
  else {
    int x = Par[v][d][t];
    Solve(x, d - 1, t, v);
    A[v] = A[x];
    for (int u : adj[v])
      if (u != prev && u != x) {
        int f = min(min(dp[u][d - 1][0], dp[u][d][0]), dp[u][d + 1][1]);
        if (f == dp[u][d - 1][0])
          Solve(u, d - 1, 0, v);
        else if (f == dp[u][d][0])
          Solve(u, d, 0, v);
        else
          Solve(u, d + 1, 1, v);
      }
    return;
  }
  if (t == 1) {
    for (int u : adj[v]) {
      if (u != prev) {
        int f = min(min(dp[u][d + 1][1], dp[u][d][0]), dp[u][d - 1][0]);
        if (f == dp[u][d + 1][1])
          Solve(u, d + 1, 1, v);
        else if (f == dp[u][d][0])
          Solve(u, d, 0, v);
        else
          Solve(u, d - 1, 0, v);
      }
    }
    return;
  }
  for (int u : adj[v]) {
    if (u == prev) continue;
    int f = min(dp[u][0][1], dp[u][1][1]);
    if (f == dp[u][0][0])
      Solve(u, 0, 0, v);
    else
      Solve(u, 1, 1, v);
  }
}
int main() {
  memset(dp, 63, sizeof(dp));
  scanf("%d %d", &n, &k);
  for (int i = 1; i < n; ++i) scanf("%d", C + i);
  for (int v, u, i = 1; i < n; ++i) {
    scanf("%d %d", &v, &u);
    adj[v].push_back(u);
    adj[u].push_back(v);
  }
  dfs(1);
  int best = 0;
  int val = dp[1][0][0];
  for (int i = 1; i < n; ++i)
    if (dp[1][i][0] < val) best = i, val = dp[1][i][0];
  printf("%d\n", val);
  Solve(1, best, 0);
  for (int i = 1; i <= n; ++i) printf("%d ", A[i]);
  printf("\n");
  return 0;
}
