#include <bits/stdc++.h>
using namespace std;
long long cm[400];
vector<vector<int> > adj;
int parent[400];
int height[400];
void treeifization(int node) {
  height[node] = 1;
  for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i)) {
    if (adj[node][i] == parent[node]) continue;
    parent[adj[node][i]] = node;
    treeifization(adj[node][i]);
    height[node] = max((height[node]), (1 + height[adj[node][i]]));
  }
}
long long newcost;
long long dp[2][405][405];
enum Action {
  kFollowFather = 0,
  kCreateNew = 1,
  kContinue = 2,
  kNewAtChild = 3
};
int continue_to[2][405][405];
int new_at[2][405][405];
int new_depth[2][405][405];
Action backtrack[2][405][405];
enum { kNone = 400 };
int center[405];
int Backtrack(int node, int distance, int type, int from) {
  Action bt = backtrack[type][node][distance];
  int conto = continue_to[type][node][distance];
  int newat = new_at[type][node][distance];
  int newdepth = new_depth[type][node][distance];
  if (bt == kCreateNew) {
    center[node] = node;
    for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i))
      if (parent[adj[node][i]] == node) {
        Backtrack(adj[node][i], 1, 1, node);
      }
    return node;
  }
  if (bt == kFollowFather) {
    center[node] = from;
    for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i))
      if (parent[adj[node][i]] == node) {
        Backtrack(adj[node][i], distance + 1, 1, from);
      }
    return from;
  }
  if (bt == kContinue) {
    center[node] = Backtrack(conto, distance - 1, 0, -1);
    for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i))
      if (parent[adj[node][i]] == node) {
        if (adj[node][i] == conto) continue;
        Backtrack(adj[node][i], distance + 1, 1, center[node]);
      }
    return center[node];
  }
  if (bt == kNewAtChild) {
    center[node] = Backtrack(newat, newdepth - 1, 0, -1);
    for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i))
      if (parent[adj[node][i]] == node) {
        if (adj[node][i] == newat) continue;
        Backtrack(adj[node][i], newdepth + 1, 1, center[node]);
      }
    return center[node];
  }
  return -3;
}
long long Solve(int node, long long distance, int type) {
  if (dp[type][node][distance] != -1LL) return dp[type][node][distance];
  long long& alias = dp[type][node][distance];
  Action& backalias = backtrack[type][node][distance];
  int& new_depth_alias = new_depth[type][node][distance];
  int& new_at_alias = new_at[type][node][distance];
  int& continue_to_alias = continue_to[type][node][distance];
  if (type == 0) {
    if (distance == 0) {
      long long totalcost = newcost;
      for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i))
        if (parent[adj[node][i]] == node) {
          totalcost += Solve(adj[node][i], 1, 1);
        }
      backalias = kCreateNew;
      return alias = totalcost;
    } else {
      long long totalcost = cm[distance];
      for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i))
        if (parent[adj[node][i]] == node) {
          totalcost += Solve(adj[node][i], distance + 1, 1);
        }
      long long bestcost = (long long)1023123123 * (long long)1023123123;
      for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i))
        if (parent[adj[node][i]] == node) {
          long long newcost = totalcost - Solve(adj[node][i], distance + 1, 1) +
                              Solve(adj[node][i], distance - 1, 0);
          if (newcost < bestcost) {
            bestcost = newcost;
            backalias = kContinue;
            continue_to_alias = adj[node][i];
          }
        }
      return alias = bestcost;
    }
  } else {
    long long bestcost = newcost;
    for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i))
      if (parent[adj[node][i]] == node) {
        bestcost += Solve(adj[node][i], 1, 1);
      }
    backalias = kCreateNew;
    if (distance != kNone) {
      long long trycost = cm[distance];
      for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i))
        if (parent[adj[node][i]] == node) {
          trycost += Solve(adj[node][i], distance + 1, 1);
        }
      if (trycost < bestcost) {
        bestcost = trycost;
        backalias = kFollowFather;
      }
    }
    for (int z = 1; z < height[node]; ++z) {
      long long trycost = cm[z];
      for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i))
        if (parent[adj[node][i]] == node) {
          trycost += Solve(adj[node][i], 1 + z, 1);
        }
      for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i))
        if (parent[adj[node][i]] == node) {
          long long newcost = trycost - Solve(adj[node][i], 1 + z, 1) +
                              Solve(adj[node][i], z - 1, 0);
          if (newcost < bestcost) {
            bestcost = newcost;
            backalias = kNewAtChild;
            new_at_alias = adj[node][i];
            new_depth_alias = z;
          }
        }
    }
    return alias = bestcost;
  }
}
int main() {
  for (int(i) = 0; (i) < (405); ++(i))
    for (int(j) = 0; (j) < (405); ++(j))
      for (int(k) = 0; (k) < (2); ++(k)) dp[k][i][j] = -1LL;
  int n, k;
  cin >> n >> k;
  newcost = k;
  for (int(i) = 0; (i) < (n - 1); ++(i)) {
    cin >> cm[i + 1];
  }
  adj = vector<vector<int> >(n);
  for (int(i) = 0; (i) < (n - 1); ++(i)) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  parent[0] = -1;
  treeifization(0);
  cout << Solve(0, kNone, 1) << endl;
  int none = Backtrack(0, kNone, 1, -5);
  for (int(i) = 0; (i) < (n); ++(i)) {
    if (i) cout << " ";
    cout << center[i] + 1;
  }
  cout << endl;
  return 0;
}
