#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9 + 29;
const int N = 2e2 + 22;
int dist[N][N], d[N], dp[N], ans[N], dp2[N][N];
set<int> vert[N];
vector<int> g[N];
void setdfs(int v, int p) {
  for (int u : g[v]) {
    if (u != p) setdfs(u, v);
  }
  vert[v].insert(v);
  for (int x : vert[v]) {
    vert[p].insert(x);
  }
}
int dfs2(int v, int p, int x, int flg) {
  int sum = d[dist[v][x]];
  for (int u : g[v]) {
    if (u != p) {
      if (flg && vert[u].count(x))
        sum += dfs2(u, v, x, 1);
      else
        sum += dfs2(u, v, x, 0);
    }
  }
  if (!flg) sum = min(sum, dp[v]);
  return sum;
}
void dfs(int v, int p) {
  for (int u : g[v]) {
    if (u != p) dfs(u, v);
  }
  int ret = inf;
  for (int x : vert[v]) {
    ret = min(ret, dfs2(v, p, x, 1));
  }
  dp[v] = ret;
  return;
}
void backTrack(int v, int p, int x, int flg) {
  if (!flg) {
    if (dfs2(v, p, x, 1) <= dp[v]) {
      ans[v] = x;
      for (int u : g[v]) {
        if (u != p) backTrack(u, v, x, 0);
      }
      return;
    }
    for (int y : vert[v]) {
      if (dfs2(v, p, y, 1) == dp[v]) {
        return backTrack(v, p, y, 1);
      }
    }
  }
  ans[v] = x;
  for (int u : g[v]) {
    if (u != p) {
      if (vert[u].count(x))
        backTrack(u, v, x, 1);
      else
        backTrack(u, v, x, 0);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout << setprecision(32);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> d[i];
  }
  memset(dist, 0x3f, sizeof(dist));
  dist[1][1] = 0;
  for (int i = 2; i <= n; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
    dist[i][i] = 0;
    dist[u][v] = dist[v][u] = 1;
  }
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  setdfs(1, 0);
  dfs(1, 0);
  backTrack(1, 0, 1, 0);
  cout << dp[1] << endl;
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
  return 0;
}
