#include <bits/stdc++.h>
int min(int a, int b) { return a < b ? a : b; }
int *ej[180], eo[180];
void append(int i, int j) {
  int o = eo[i]++;
  if (o >= 2 && (o & o - 1) == 0)
    ej[i] = (int *)realloc(ej[i], o * 2 * sizeof *ej[i]);
  ej[i][o] = j;
}
int cc[180], dp[180][180][2], jj[180][180], diff[180][180], n;
void dfs(int p, int i) {
  int o, d;
  memset(jj[i], -1, n * sizeof *jj[i]),
      memset(diff[i], 0x3f, n * sizeof *diff[i]), diff[i][0] = 0;
  for (o = eo[i]; o--;) {
    int j = ej[i][o];
    if (j != p) {
      dfs(i, j);
      for (d = 0; d < n; d++) {
        int x = min(min(dp[j][d][0], d == 0 ? 0x3f3f3f3f : dp[j][d - 1][0]),
                    d + 1 == n ? 0x3f3f3f3f : dp[j][d + 1][1]);
        dp[i][d][1] = min(dp[i][d][1] + x, 0x3f3f3f3f);
        if (d > 0 && dp[j][d - 1][0] != 0x3f3f3f3f &&
            diff[i][d] > dp[j][d - 1][0] - x)
          diff[i][d] = dp[j][d - 1][0] - x, jj[i][d] = j;
      }
    }
  }
  for (d = 0; d < n; d++) {
    dp[i][d][1] = min(dp[i][d][1] + cc[d], 0x3f3f3f3f);
    dp[i][d][0] = min(dp[i][d][1] + diff[i][d], 0x3f3f3f3f);
  }
}
int pp[180];
void trace(int p, int i, int d, int up) {
  int o;
  if (d == 0)
    pp[i] = i;
  else if (up)
    pp[i] = pp[p];
  else
    trace(i, jj[i][d], d - 1, 0), pp[i] = pp[jj[i][d]];
  for (o = eo[i]; o--;) {
    int j = ej[i][o];
    if (j != p && (up || j != jj[i][d])) {
      int x = min(min(dp[j][d][0], d == 0 ? 0x3f3f3f3f : dp[j][d - 1][0]),
                  d + 1 == n ? 0x3f3f3f3f : dp[j][d + 1][1]);
      if (dp[j][d][0] == x)
        trace(i, j, d, 0);
      else if (d > 0 && dp[j][d - 1][0] == x)
        trace(i, j, d - 1, 0);
      else
        trace(i, j, d + 1, 1);
    }
  }
}
int main() {
  int h, i, j, d, d_, ans;
  scanf("%d", &n);
  for (d = 0; d < n; d++) scanf("%d", &cc[d]);
  for (i = 0; i < n; i++) ej[i] = (int *)malloc(2 * sizeof *ej[i]);
  for (h = 0; h < n - 1; h++) {
    scanf("%d%d", &i, &j), i--, j--;
    append(i, j), append(j, i);
  }
  dfs(-1, 0);
  ans = 0x3f3f3f3f, d_ = -1;
  for (d = 0; d < n; d++) {
    int x = dp[0][d][0];
    if (ans > x) ans = x, d_ = d;
  }
  printf("%d\n", ans);
  trace(-1, 0, d_, 0);
  for (i = 0; i < n; i++) printf("%d ", pp[i] + 1);
  printf("\n");
  return 0;
}
