#include <bits/stdc++.h>   using namespace std;   const int maxn = 180 + 10;   const int oo = 1000000000;   int opt[maxn][maxn * 2];   int c[maxn][maxn * 2], cc[maxn][maxn * 2];   int e[maxn][maxn];   int n, kk, d[maxn];   int father[maxn];   int res[maxn];   void dp(int u) {     for (int v = 1; v <= n; v++)       if (e[u][v] && v == father[u]) e[u][v] = 0;     for (int v = 1; v <= n; v++)       if (e[u][v]) {         father[v] = u;         dp(v);       }     for (int i = 1; i <= n; i++) {       int w = i - n, o = 0;       for (int v = 1; v <= n; v++)         if (e[u][v]) {           int o2 = opt[v][i - 1];           for (int j = n; j <= n * 2; j++) o2 = min(o2, opt[v][j]);           o += o2;           o = min(o, oo);         }       if (w == 0)         o += kk;       else         o += d[-w];       opt[u][i] = o;     }     int best[maxn];     for (int i = n + 1; i < n * 2; i++) {       for (int v = 1; v <= n; v++)         if (e[u][v]) {           best[v] = oo;           for (int j = i - 1; j <= n * 2; j++) best[v] = min(best[v], opt[v][j]);           best[v] = min(best[v], opt[v][n + n - i - 1]);         }       for (int v = 1; v <= n; v++)         if (e[u][v]) {           int o = opt[v][i - 1];           for (int w = 1; w <= n; w++)             if (w != v && e[u][w]) {               o += best[w];               o = min(o, oo);             }           o += d[i - n];           if (o < opt[u][i]) {             opt[u][i] = o;             cc[u][i] = v;           }         }     }   }   void dfs(int u, int w, int p) {     if (w == n) p = u;     if (w <= n) {       res[u] = p;       for (int v = 1; v <= n; v++)         if (e[u][v]) {           int o = w - 1;           for (int j = n; j <= n * 2; j++)             if (opt[v][j] < opt[v][o]) o = j;           dfs(v, o, p);         }     } else {       int o = cc[u][w];       dfs(o, w - 1, p);       res[u] = res[o];       for (int v = 1; v <= n; v++)         if (v != o && e[u][v]) {           int _o = n + n - w - 1;           for (int j = w - 1; j <= n * 2; j++)             if (opt[v][j] < opt[v][_o]) _o = j;           dfs(v, _o, res[u]);         }     }   }   int main() {     scanf( %d%d , &n, &kk);     for (int i = 1; i < n; i++) scanf( %d , &d[i]);     for (int i = 1, u, v; i < n; i++) {       scanf( %d%d , &u, &v);       e[u][v] = e[v][u] = 1;     }     for (int i = 1; i <= n; i++)       for (int j = 0; j <= n * 2 + 1; j++) opt[i][j] = oo;     dp(1);     int best = n;     for (int i = n; i <= n * 2; i++)       if (opt[1][i] < opt[1][best]) best = i;     dfs(1, best, 0);     printf( %d n , opt[1][best]);     for (int i = 1; i <= n; i++) printf( %d%c , res[i], i == n ?   n  :    );   }   