#include <bits/stdc++.h>
using namespace std;
int n, k;
int d[188];
int par[188];
vector<int> g[188];
int dp[188][188];
int pos[188];
int ans[188];
void build(int x, int pre) {
  par[x] = pre;
  for (int i = (0); i < (g[x].size()); ++i) {
    int to = g[x][i];
    if (to == pre) {
      g[x].erase(g[x].begin() + i, g[x].begin() + i + 1);
      i--;
      continue;
    }
    build(to, x);
  }
}
void dfs(int x) {
  for (int i = (0); i < (g[x].size()); ++i) {
    int to = g[x][i];
    dfs(to);
  }
  for (int y = (0); y < (n); ++y) {
    int z = y;
    while (z != x && z != -1) z = par[z];
    if (z == -1) continue;
    z = y;
    int cur = 0, lst = -1, dis = 0;
    while (1) {
      cur += (dis ? d[dis] : k);
      dis++;
      for (int i = (0); i < (g[z].size()); ++i) {
        int to = g[z][i];
        if (to == lst) continue;
        cur += dp[to][dis];
      }
      if (z == x) break;
      lst = z;
      z = par[z];
    }
    if (cur < dp[x][0]) {
      dp[x][0] = cur;
      pos[x] = y;
    }
  }
  for (int dis = (1); dis < (n); ++dis) {
    dp[x][dis] = dp[x][0];
    int cur = d[dis];
    for (int i = (0); i < (g[x].size()); ++i) {
      int to = g[x][i];
      cur += dp[to][dis + 1];
    }
    if (cur < dp[x][dis]) {
      dp[x][dis] = cur;
    }
  }
}
void getans(int x, int dis, int lst) {
  if (dp[x][dis] != dp[x][0]) {
    ans[x] = lst;
    for (int i = (0); i < (g[x].size()); ++i) {
      int to = g[x][i];
      getans(to, dis + 1, lst);
    }
    return;
  }
  int y = pos[x];
  int z = y;
  dis = 0;
  lst = -1;
  while (1) {
    ans[z] = y;
    dis++;
    for (int i = (0); i < (g[z].size()); ++i) {
      int to = g[z][i];
      if (to == lst) continue;
      getans(to, dis, y);
    }
    if (z == x) break;
    lst = z;
    z = par[z];
  }
}
int main() {
  memset(dp, 0x3f, sizeof(dp));
  cin >> n >> k;
  for (int i = (1); i < (n); ++i) cin >> d[i];
  for (int i = (1); i < (n); ++i) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  build(0, -1);
  dfs(0);
  cout << dp[0][0] << endl;
  getans(0, 0, -1);
  for (int i = (0); i < (n); ++i) {
    cout << ans[i] + 1 << (i == n - 1 ? '\n' : ' ');
  }
  return 0;
}
