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;
namespace IO {
const int sz = 1 << 15;
char inbuf[sz], outbuf[sz];
char *pinbuf = inbuf + sz;
char *poutbuf = outbuf;
inline char _getchar() {
  if (pinbuf == inbuf + sz) fread(inbuf, 1, sz, stdin), pinbuf = inbuf;
  return *(pinbuf++);
}
inline void _putchar(char x) {
  if (poutbuf == outbuf + sz) fwrite(outbuf, 1, sz, stdout), poutbuf = outbuf;
  *(poutbuf++) = x;
}
inline void flush() {
  if (poutbuf != outbuf)
    fwrite(outbuf, 1, poutbuf - outbuf, stdout), poutbuf = outbuf;
}
}  // namespace IO
inline int read() {
  int x = 0, p = 1;
  char c = IO::_getchar();
  while (c < '0' || c > '9') {
    if (c == '-') p = -1;
    c = IO::_getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = IO::_getchar();
  return x * p;
}
namespace Mymath {
long long qp(long long x, long long p, long long mod) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = ans * x % mod;
    x = x * x % mod;
    p >>= 1;
  }
  return ans;
}
long long inv(long long x, long long mod) { return qp(x, mod - 2, mod); }
long long C(long long N, long long K, long long fact[], long long mod) {
  return fact[N] * inv(fact[K], mod) % mod * inv(fact[N - K], mod) % mod;
}
template <typename Tp>
Tp gcd(Tp A, Tp B) {
  if (B == 0) return A;
  return gcd(B, A % B);
}
template <typename Tp>
Tp lcm(Tp A, Tp B) {
  return A * B / gcd(A, B);
}
};  // namespace Mymath
namespace fwt {
using namespace Mymath;
void FWT(int a[], int n, long long mod) {
  for (int d = 1; d < n; d <<= 1)
    for (int m = d << 1, i = 0; i < n; i += m)
      for (int j = 0; j < d; j++) {
        int x = a[i + j], y = a[i + j + d];
        a[i + j] = (x + y) % mod, a[i + j + d] = (x - y + mod) % mod;
      }
}
void UFWT(int a[], int n, long long mod) {
  long long rev = inv(2, mod);
  for (int d = 1; d < n; d <<= 1)
    for (int m = d << 1, i = 0; i < n; i += m)
      for (int j = 0; j < d; j++) {
        int x = a[i + j], y = a[i + j + d];
        a[i + j] = 1LL * (x + y) * rev % mod,
              a[i + j + d] = (1LL * (x - y) * rev % mod + mod) % mod;
      }
}
void solve(int a[], int b[], int n, long long mod) {
  FWT(a, n, mod);
  FWT(b, n, mod);
  for (int i = 0; i < n; i++) a[i] = 1LL * a[i] * b[i] % mod;
  UFWT(a, n, mod);
}
};  // namespace fwt
namespace Maxflow {
const int Maxn = 1005;
struct edge {
  int to, rev, cap;
  edge(int _to, int _rev, int _cap) { to = _to, rev = _rev, cap = _cap; }
};
int src = 1002, snk = 1003;
vector<edge> G[Maxn];
int dist[Maxn], seen[Maxn];
int n;
void Clear() {
  for (int i = 0; i < Maxn; i++) G[i].clear();
}
void bfs(int s) {
  for (int i = 0; i < Maxn; i++) dist[i] = -1;
  dist[s] = 0;
  queue<int> Q;
  Q.push(s);
  while (!Q.empty()) {
    int x = Q.front();
    Q.pop();
    for (int i = 0; i < G[x].size(); i++) {
      edge &e = G[x][i];
      if (e.cap && dist[e.to] == -1) {
        dist[e.to] = dist[x] + 1;
        Q.push(e.to);
      }
    }
  }
}
int dfs(int now, int dest, int fl) {
  if (now == dest) return fl;
  for (int &i = seen[now]; i < G[now].size(); i++) {
    edge &ed = G[now][i];
    if (ed.cap && dist[ed.to] == dist[now] + 1) {
      int f = dfs(ed.to, dest, min(fl, ed.cap));
      if (f) {
        ed.cap -= f;
        G[ed.to][ed.rev].cap += f;
        return f;
      }
    }
  }
  return 0;
}
int dinic(int s = src, int t = snk) {
  int ret = 0;
  while (1) {
    memset(seen, 0, sizeof(seen));
    bfs(s);
    if (dist[t] == -1) return ret;
    int f = dfs(s, t, 2147483647);
    while (f) {
      ret += f;
      f = dfs(s, t, 2147483647);
    }
  }
}
};  // namespace Maxflow
namespace Geometry {
struct iP {
  long long x, y;
  iP(long long _x, long long _y) { x = _x, y = _y; }
  iP() { x = y = 0; }
  iP operator+(iP p) { return iP(x + p.x, y + p.y); }
  iP operator-(iP p) { return iP(x - p.x, y - p.y); }
  iP operator*(long long k) { return iP(x * k, y * k); }
  long long det(iP p) { return x * p.y - y * p.x; }
  long long dot(iP p) { return x * p.x + y * p.y; }
  long long dist() { return x * x + y * y; }
  bool operator<(const iP &p) const {
    if (x != p.x) return x < p.x;
    return y < p.y;
  }
};
struct dP {
  double x, y;
  dP(double _x, double _y) { x = _x, y = _y; }
  dP() { x = y = 0.0; }
  dP operator+(dP p) { return dP(x + p.x, y + p.y); }
  dP operator-(dP p) { return dP(x - p.x, y - p.y); }
  dP operator*(double k) { return dP(x * k, y * k); }
  double det(dP p) { return x * p.y - y * p.x; }
  double dot(dP p) { return x * p.x + y * p.y; }
  double dist() { return x * x + y * y; }
  bool operator<(const dP &p) const {
    if (x != p.x) return x < p.x;
    return y < p.y;
  }
};
vector<iP> convex_hull(iP X[], int l) {
  vector<iP> ret;
  sort(X + 1, X + 1 + l);
  ret.push_back(X[1]);
  for (int i = 2; i <= l; i++) {
    while (ret.size() >= 2 &&
           (ret[ret.size() - 2] - X[i]).det(ret[ret.size() - 1] - X[i]) >= 0) {
      ret.pop_back();
    }
    ret.push_back(X[i]);
  }
  int rs = ret.size() + 1;
  for (int i = l - 1; i >= 1; i--) {
    while (ret.size() >= rs &&
           (ret[ret.size() - 2] - X[i]).det(ret[ret.size() - 1] - X[i]) >= 0) {
      ret.pop_back();
    }
    ret.push_back(X[i]);
  }
  return ret;
}
};  // namespace Geometry
const int Maxn = 188;
int n, k;
int d[Maxn];
int par[Maxn];
vector<int> G[Maxn], son[Maxn], str[Maxn];
int dp[Maxn][Maxn];
int ans[Maxn];
int pre[Maxn][Maxn];
void pre_dfs(int x, int p) {
  par[x] = p;
  str[x].push_back(x);
  for (int i = 0; i < G[x].size(); i++) {
    int u = G[x][i];
    if (u != p) {
      son[x].push_back(u);
      pre_dfs(u, x);
      for (auto v : str[u]) {
        str[x].push_back(v);
      }
    }
  }
}
void dfs(int x) {
  for (int i = 0; i < son[x].size(); i++) {
    int v = son[x][i];
    dfs(v);
  }
  dp[x][0] = 1e9;
  for (auto v : str[x]) {
    int cost = 0, di = 0;
    int u = v, prev = -1;
    for (; u != par[x]; prev = u, u = par[u]) {
      if (di == 0)
        cost += k, di++;
      else
        cost += d[di++];
      for (auto w : son[u]) {
        if (w != prev) cost += dp[w][min(di, n - 1)];
      }
    }
    if (cost < dp[x][0]) {
      dp[x][0] = cost;
      pre[x][0] = v;
    }
  }
  for (int i = 1; i < n; i++) {
    dp[x][i] = dp[x][0];
    pre[x][i] = 0;
    int tmp = d[i];
    for (auto v : son[x]) {
      tmp += dp[v][min(i + 1, n - 1)];
    }
    if (tmp < dp[x][i]) {
      dp[x][i] = tmp;
      pre[x][i] = 1;
    }
  }
}
void traverse(int x, int d, int c) {
  if (d != 0 && pre[x][d] == 0) {
    traverse(x, 0, -1);
    return;
  }
  if (d != 0) {
    ans[x] = c;
    for (auto v : son[x]) {
      traverse(v, d + 1, c);
    }
    return;
  }
  ans[x] = pre[x][0];
  int v = pre[x][0], prev = -1, di = 0;
  for (; v != par[x]; prev = v, v = par[v]) {
    for (auto w : son[v]) {
      if (w != prev) {
        traverse(w, di + 1, pre[x][0]);
      }
    }
    ans[v] = pre[x][0];
    di++;
  }
}
int main() {
  n = read();
  k = read();
  for (int i = 1; i <= n - 1; i++) d[i] = read();
  for (int i = 0; i < n - 1; i++) {
    int u = read(), v = read();
    G[u].push_back(v);
    G[v].push_back(u);
  }
  pre_dfs(1, -1);
  dfs(1);
  printf("%d\n", dp[1][0]);
  traverse(1, 0, -1);
  for (int i = 1; i <= n; i++) {
    printf("%d ", ans[i]);
  }
  printf("\n");
  return 0;
}