Problem: Thought it is already the XXI century, the Mass Media isn't very popular in Walrusland. The cities get news from messengers who can only travel along roads. The network of roads in Walrusland is built so that it is possible to get to any city from any other one in exactly one way, and the roads' lengths are equal.

The North Pole governor decided to carry out an information reform. Several cities were decided to be chosen and made regional centers. Maintaining a region center takes k fishlars (which is a local currency) per year. It is assumed that a regional center always has information on the latest news.

For every city which is not a regional center, it was decided to appoint a regional center which will be responsible for keeping this city informed. In that case the maintenance costs will be equal to dlen fishlars per year, where len is the distance from a city to the corresponding regional center, measured in the number of roads along which one needs to go.

Your task is to minimize the costs to carry out the reform.

Input

The first line contains two given numbers n and k (1 ≤ n ≤ 180, 1 ≤ k ≤ 105).

The second line contains n - 1 integers di, numbered starting with 1 (di ≤ di + 1, 0 ≤ di ≤ 105).

Next n - 1 lines contain the pairs of cities connected by a road.

Output

On the first line print the minimum number of fishlars needed for a year's maintenance. On the second line print n numbers, where the i-th number will represent the number of the regional center, appointed to the i-th city. If the i-th city is a regional center itself, then you should print number i.

If there are several solutions to that problem, print any of them.

Examples

Input

8 10
2 5 9 11 15 19 20
1 4
1 3
1 7
4 6
2 8
2 3
3 5


Output

38
3 3 3 4 3 4 3 3 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAX = 250;
long long dp[2][MAX][MAX];
long long gdeep;
long long deeps[MAX], deeps2[MAX], vist[MAX], store[MAX][MAX], stidx[MAX][MAX],
    parent[MAX];
vector<long long> childs[MAX];
long long head[MAX], nxt[MAX << 1], to[MAX << 1], ent, cur;
long long n, k, d[MAX];
struct node {
  long long mask, v, deep;
  node() {}
  node(long long a, long long b, long long c) : mask(a), v(b), deep(c) {}
};
vector<node> ss[2][MAX][MAX];
void add(long long a, long long b) {
  nxt[ent] = head[a], to[ent] = b, head[a] = ent++;
  nxt[ent] = head[b], to[ent] = a, head[b] = ent++;
}
void dfs1(long long v, long long pa) {
  vist[v] = 1;
  deeps[v] = 0;
  for (long long i = head[v]; ~i; i = nxt[i]) {
    long long u = to[i];
    if (u != pa && vist[u] == 0) {
      parent[u] = v;
      dfs1(u, v);
      deeps[v] = std::max(deeps[v], deeps[u] + 1);
    }
  }
}
void dfs2(long long v, long long pa) {
  vist[v] = 1;
  for (long long i = head[v]; ~i; i = nxt[i]) {
    long long u = to[i];
    if (u != pa && vist[u] == 0) {
      childs[v].push_back(u);
      dfs2(u, v);
    }
  }
}
bool debug = 0;
long long sol(long long mask, long long v, long long deep) {
  auto &ele = dp[mask][v][deep];
  auto &ve = ss[mask][v][deep];
  if (ele != -1) return ele;
  if (mask == 0) {
    if (vist[v] == 0) {
      vist[v] = 1;
      for (long long i = 0; i < childs[v].size(); i++) {
        long long u = childs[v][i];
        for (long long dd = 0; dd <= deeps[u]; dd++) {
          sol(mask, u, dd);
        }
        store[u][deeps[u]] = dp[mask][u][deeps[u]],
        stidx[u][deeps[u]] = deeps[u];
        for (long long dd = deeps[u] - 1; dd >= 0; dd--) {
          if (store[u][dd + 1] > dp[mask][u][dd]) {
            store[u][dd] = dp[mask][u][dd], stidx[u][dd] = dd;
          } else
            store[u][dd] = store[u][dd + 1], stidx[u][dd] = stidx[u][dd + 1];
        }
      }
    }
    if (childs[v].size() == 0) {
      if (deep == 0)
        return ele = k;
      else
        return ele = LLONG_MAX;
    } else {
      if (deep == 0) {
        ele = k;
        for (long long i = 0; i < childs[v].size(); i++) {
          long long u = childs[v][i];
          ele += std::min(sol(1, u, 1) - k, store[u][0]);
          if (sol(1, u, 1) - k < store[u][0])
            ve.push_back({1, u, 1});
          else
            ve.push_back({0, u, stidx[u][0]});
        }
        return ele;
      } else {
        if (deep > deeps[v]) return ele = LLONG_MAX;
        ele = LLONG_MAX;
        for (long long i = 0; i < childs[v].size(); i++) {
          long long u = childs[v][i];
          if (deeps[u] >= deep - 1) {
            vector<node> tmp;
            long long t1 = sol(0, u, deep - 1);
            tmp.push_back({0, u, deep - 1});
            if (t1 != LLONG_MAX) {
              for (long long j = 0; j < childs[v].size(); j++) {
                long long t = childs[v][j];
                if (t != u) {
                  if (deep - 1 > deeps[t])
                    t1 += sol(1, t, deep + 1) - k,
                        tmp.push_back({1, t, deep + 1});
                  else {
                    if (sol(1, t, deep + 1) - k < store[t][deep - 1])
                      t1 += sol(1, t, deep + 1) - k,
                          tmp.push_back({1, t, deep + 1});
                    else
                      t1 += store[t][deep - 1],
                          tmp.push_back({0, t, stidx[t][deep - 1]});
                  }
                }
              }
              if (t1 + d[deep] < ele) {
                ele = t1 + d[deep];
                ve = move(tmp);
              }
            }
          }
        }
        return ele;
      }
    }
  } else {
    if (childs[v].size() == 0) {
      if (deep > deeps2[v])
        return ele = LLONG_MAX;
      else
        return ele = d[deep] + k;
    } else {
      if (deep > deeps2[v]) return ele = LLONG_MAX;
      ele = d[deep] + k;
      for (int i = 0; i < childs[v].size(); i++) {
        long long u = childs[v][i];
        long long t1 = sol(mask, u, deep + 1) - k;
        long long t2 = LLONG_MAX, idx;
        for (long long dd = 0; dd <= deeps[u]; dd++) {
          if (sol(0, u, dd) < t2) {
            t2 = sol(0, u, dd), idx = dd;
          }
        }
        if (t1 < t2) {
          ele += t1, ve.push_back({mask, u, deep + 1});
        } else
          ele += t2, ve.push_back({0, u, idx});
      }
      return ele;
    }
  }
}
void printdp() {
  printf("parentinfo\n");
  for (int i = 1; i <= n; i++) printf("i = %d, pa = %lld\n", i, parent[i]);
  printf("deepinfo\n");
  for (int i = 1; i <= n; i++) printf("i = %d, dd = %lld\n", i, deeps[i]);
  printf("deep2info\n");
  for (int i = 1; i <= n; i++) printf("i = %d, dd = %lld\n", i, deeps2[i]);
  for (int i = 1; i <= n; i++) {
    printf("*********************i = %d :\n", i);
    for (int dd = 0; dd <= deeps[i]; dd++) {
      printf("(%d, %d, %d) = %lld\n", 0, i, dd, dp[0][i][dd]);
    }
    for (int dd = 0; dd <= deeps2[i]; dd++) {
      printf("(%d, %d, %d) = %lld\n", 1, i, dd, dp[1][i][dd]);
    }
  }
}
bool power[MAX];
long long ans[MAX];
void assignP(long long mask, long long v, long long deep) {
  auto &ve = ss[mask][v][deep];
  if (mask == 0 && deep == 0) power[v] = 1;
  for (int i = 0; i < ve.size(); i++) {
    node &nn = ve[i];
    assignP(nn.mask, nn.v, nn.deep);
  }
}
void bfs() {
  for (int i = 1; i <= n; i++) {
    memset(vist, 0, sizeof(vist));
    queue<int> q;
    q.push(i), vist[i] = 1;
    if (power[i] == 1)
      ans[i] = i;
    else {
      bool find = 0;
      while (!q.empty() && !find) {
        int v = q.front();
        q.pop();
        for (int j = head[v]; ~j; j = nxt[j]) {
          int u = to[j];
          if (vist[u] == 0) {
            if (power[u] == 1) {
              ans[i] = u, find = 1;
              break;
            } else {
              vist[u] = 1, q.push(u);
            }
          }
        }
      }
    }
  }
}
int main() {
  scanf("%lld%lld", &n, &k);
  for (long long i = 1; i <= n - 1; i++) scanf("%lld", &d[i]);
  memset(head, -1, sizeof(head));
  ent = 0;
  for (long long i = 1; i <= n - 1; i++) {
    long long a, b;
    scanf("%lld%lld", &a, &b);
    add(a, b);
  }
  gdeep = LLONG_MIN;
  for (long long i = 1; i <= n; i++) deeps[i] = LLONG_MIN;
  memset(vist, 0, sizeof(vist));
  parent[1] = -1, dfs1(1, -1);
  for (long long i = 1; i <= n; i++) {
    deeps2[i] = 0;
    long long tt = i, zz = 1;
    if (i == 2)
      debug = 1;
    else
      debug = 0;
    while (tt != -1) {
      long long pa = parent[tt];
      if (pa != -1) {
        deeps2[i] = std::max(deeps2[i], zz);
        for (long long j = head[pa]; ~j; j = nxt[j]) {
          long long u = to[j];
          if (u != tt && u != parent[pa]) {
            deeps2[i] = std::max(deeps2[i], deeps[u] + zz + 1);
          }
        }
      }
      ++zz, tt = pa;
    }
  }
  memset(vist, 0, sizeof(vist));
  dfs2(1, -1);
  for (long long i = 1; i <= n; i++) {
    for (long long dd = 0; dd <= deeps[i]; dd++) dp[0][i][dd] = -1;
    for (long long dd = 0; dd <= deeps2[i]; dd++) dp[1][i][dd] = -1;
  }
  memset(vist, 0, sizeof(vist));
  long long opt = LLONG_MAX, t1;
  node optn;
  for (long long dd = 0; dd <= deeps[1]; dd++) {
    t1 = sol(0, 1, dd);
    if (t1 < opt) opt = t1, optn = {0, 1, dd};
  }
  for (long long dd = 1; dd <= deeps2[1]; dd++) {
    t1 = sol(1, 1, dd);
    if (t1 < opt) opt = t1, optn = {1, 1, dd};
  }
  printf("%lld\n", opt);
  memset(power, 0, sizeof(power));
  assignP(optn.mask, optn.v, optn.deep);
  bfs();
  for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
  printf("\n");
  return 0;
}