#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
pair<int, int> Time[1003];
vector<int> edge[1003];
int d[207][207];
int f[207][207], where[207], belong[207][207];
int W[1003], N, K, totalTime;
void surf(int u, int Fa) {
  Time[u].first = totalTime++;
  for (typeof(edge[u].begin()) it = edge[u].begin(); it != edge[u].end(); it++)
    if (*it != Fa) surf(*it, u);
  Time[u].second = totalTime;
}
queue<int> q;
void dist(int u, int d[]) {
  while (!q.empty()) q.pop();
  q.push(u);
  for (int i = 0; i < N; i++) d[i] = 0x7f7f7f7f;
  d[u] = 0;
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    for (typeof(edge[now].begin()) it = edge[now].begin();
         it != edge[now].end(); it++)
      if (d[*it] > d[now] + 1) {
        d[*it] = d[now] + 1;
        q.push(*it);
      }
  }
}
void calc(int u, int Fa) {
  if (edge[u].size() == 1 && Fa != -1) {
    for (int i = 0; i < N; i++) f[u][i] = W[d[u][i]];
    return;
  }
  for (typeof(edge[u].begin()) it = edge[u].begin(); it != edge[u].end(); it++)
    if (*it != Fa) calc(*it, u);
  for (int i = 0; i < N; i++) {
    int partsum = W[d[u][i]];
    if (i != u && Time[i].first >= Time[u].first &&
        Time[i].second <= Time[u].second) {
      for (typeof(edge[u].begin()) it = edge[u].begin(); it != edge[u].end();
           it++) {
        if (*it == Fa) continue;
        int best = f[*it][i];
        if (!(Time[*it].first <= Time[i].first &&
              Time[*it].second >= Time[i].second))
          for (int j = 0; j < N; j++)
            if (Time[*it].first <= Time[j].first &&
                Time[*it].second >= Time[j].second)
              best = min(best, f[*it][j]);
        partsum += best;
      }
    } else {
      for (typeof(edge[u].begin()) it = edge[u].begin(); it != edge[u].end();
           it++) {
        if (*it == Fa) continue;
        int best = f[*it][i];
        for (int j = 0; j < N; j++)
          if (Time[*it].first <= Time[j].first &&
              Time[*it].second >= Time[j].second)
            best = min(best, f[*it][j]);
        partsum += best;
      }
    }
    f[u][i] = partsum;
  }
}
void output(int u, int pick, int Fa) {
  where[u] = pick;
  if (edge[u].size() == 1 && Fa != -1) return;
  int i = pick;
  {
    int partsum = W[d[u][i]];
    if (i != u && Time[i].first >= Time[u].first &&
        Time[i].second <= Time[u].second) {
      for (typeof(edge[u].begin()) it = edge[u].begin(); it != edge[u].end();
           it++) {
        if (*it == Fa) continue;
        int best = f[*it][i];
        int wherebest = i;
        if (!(Time[*it].first <= Time[i].first &&
              Time[*it].second >= Time[i].second))
          for (int j = 0; j < N; j++)
            if (Time[*it].first <= Time[j].first &&
                Time[*it].second >= Time[j].second) {
              if (f[*it][j] < best) wherebest = j;
              best = min(best, f[*it][j]);
            }
        partsum += best;
        output(*it, wherebest, u);
      }
    } else {
      for (typeof(edge[u].begin()) it = edge[u].begin(); it != edge[u].end();
           it++) {
        if (*it == Fa) continue;
        int best = f[*it][i];
        int wherebest = i;
        for (int j = 0; j < N; j++)
          if (Time[*it].first <= Time[j].first &&
              Time[*it].second >= Time[j].second) {
            if (f[*it][j] < best) wherebest = j;
            best = min(best, f[*it][j]);
          }
        partsum += best;
        output(*it, wherebest, u);
      }
    }
  }
}
int main() {
  cin >> N >> K;
  W[0] = K;
  for (int i = 0; i < N - 1; i++) cin >> W[i + 1];
  for (int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  for (int i = 0; i < N; i++) dist(i, d[i]);
  totalTime = 0;
  surf(0, -1);
  calc(0, -1);
  int ans = 0x7f7f7f7f;
  int whereisit = 0;
  for (int i = 0; i < N; i++) {
    if (f[0][i] < ans) whereisit = i;
    ans = min(ans, f[0][i]);
  }
  cout << ans << endl;
  output(0, whereisit, -1);
  for (int i = 0; i < N; i++) {
    if (i) cout << " ";
    cout << where[i] + 1;
  }
  cout << endl;
  return 0;
}
