#include <bits/stdc++.h>   using namespace std;   int n, k;   int d[188];   int par[188];   vector<int> g[188];   int dp[188][188];   int pos[188];   int ans[188];   void build(int x, int pre) {     par[x] = pre;     for (int i = (0); i < (g[x].size()); ++i) {       int to = g[x][i];       if (to == pre) {         g[x].erase(g[x].begin() + i, g[x].begin() + i + 1);         i--;         continue;       }       build(to, x);     }   }   void dfs(int x) {     for (int i = (0); i < (g[x].size()); ++i) {       int to = g[x][i];       dfs(to);     }     for (int y = (0); y < (n); ++y) {       int z = y;       while (z != x && z != -1) z = par[z];       if (z == -1) continue;       z = y;       int cur = 0, lst = -1, dis = 0;       while (1) {         cur += (dis ? d[dis] : k);         dis++;         for (int i = (0); i < (g[z].size()); ++i) {           int to = g[z][i];           if (to == lst) continue;           cur += dp[to][dis];         }         if (z == x) break;         lst = z;         z = par[z];       }       if (cur < dp[x][0]) {         dp[x][0] = cur;         pos[x] = y;       }     }     for (int dis = (1); dis < (n); ++dis) {       dp[x][dis] = dp[x][0];       int cur = d[dis];       for (int i = (0); i < (g[x].size()); ++i) {         int to = g[x][i];         cur += dp[to][dis + 1];       }       if (cur < dp[x][dis]) {         dp[x][dis] = cur;       }     }   }   void getans(int x, int dis, int lst) {     if (dp[x][dis] != dp[x][0]) {       ans[x] = lst;       for (int i = (0); i < (g[x].size()); ++i) {         int to = g[x][i];         getans(to, dis + 1, lst);       }       return;     }     int y = pos[x];     int z = y;     dis = 0;     lst = -1;     while (1) {       ans[z] = y;       dis++;       for (int i = (0); i < (g[z].size()); ++i) {         int to = g[z][i];         if (to == lst) continue;         getans(to, dis, y);       }       if (z == x) break;       lst = z;       z = par[z];     }   }   int main() {     memset(dp, 0x3f, sizeof(dp));     cin >> n >> k;     for (int i = (1); i < (n); ++i) cin >> d[i];     for (int i = (1); i < (n); ++i) {       int a, b;       cin >> a >> b;       a--;       b--;       g[a].push_back(b);       g[b].push_back(a);     }     build(0, -1);     dfs(0);     cout << dp[0][0] << endl;     getans(0, 0, -1);     for (int i = (0); i < (n); ++i) {       cout << ans[i] + 1 << (i == n - 1 ?   n  :    );     }     return 0;   }   