package main

import (
	"bufio"
	"fmt"
	"os"
)

const INF int64 = 1 << 60

var (
	n         int
	k         int64
	maxD      int
	d         []int64
	adj       [][]int
	children  [][]int
	A         [][]int64
	B         [][]int64
	bestChild [][]int
	closeCost []int64
	bestClose []int
	centerMem [][]int
	ans       []int
)

func dfs(v, p int) {
	for _, to := range adj[v] {
		if to == p {
			continue
		}
		children[v] = append(children[v], to)
		dfs(to, v)
	}
	compute(v)
}

func compute(v int) {
	for t := 1; t <= maxD; t++ {
		cost := d[t]
		for _, c := range children[v] {
			join := INF
			if t+1 <= maxD {
				join = A[c][t+1]
			}
			if join <= closeCost[c] {
				cost += join
			} else {
				cost += closeCost[c]
			}
		}
		A[v][t] = cost
	}

	cost0 := k
	for _, c := range children[v] {
		join := INF
		if 1 <= maxD {
			join = A[c][1]
		}
		if join <= closeCost[c] {
			cost0 += join
		} else {
			cost0 += closeCost[c]
		}
	}
	B[v][0] = cost0
	bestChild[v][0] = -1

	for s := 1; s <= maxD; s++ {
		sumOther := int64(0)
		for _, c := range children[v] {
			cur := closeCost[c]
			if s+1 <= maxD && A[c][s+1] < cur {
				cur = A[c][s+1]
			}
			sumOther += cur
		}

		best := INF
		who := -1
		for _, c := range children[v] {
			if B[c][s-1] >= INF/2 {
				continue
			}
			cur := closeCost[c]
			if s+1 <= maxD && A[c][s+1] < cur {
				cur = A[c][s+1]
			}
			val := d[s] + sumOther + B[c][s-1] - cur
			if val < best {
				best = val
				who = c
			}
		}
		B[v][s] = best
		bestChild[v][s] = who
	}

	closeCost[v] = B[v][0]
	bestClose[v] = 0
	for s := 1; s <= maxD; s++ {
		if B[v][s] < closeCost[v] {
			closeCost[v] = B[v][s]
			bestClose[v] = s
		}
	}
}

func getCenter(v, s int) int {
	if centerMem[v][s] != 0 {
		return centerMem[v][s]
	}
	var res int
	if s == 0 {
		res = v
	} else {
		res = getCenter(bestChild[v][s], s-1)
	}
	centerMem[v][s] = res
	return res
}

func buildA(v, t, center int) {
	ans[v] = center
	for _, c := range children[v] {
		join := INF
		if t+1 <= maxD {
			join = A[c][t+1]
		}
		if join <= closeCost[c] {
			buildA(c, t+1, center)
		} else {
			buildB(c, bestClose[c])
		}
	}
}

func buildB(v, s int) {
	center := getCenter(v, s)
	ans[v] = center
	if s == 0 {
		for _, c := range children[v] {
			join := INF
			if 1 <= maxD {
				join = A[c][1]
			}
			if join <= closeCost[c] {
				buildA(c, 1, center)
			} else {
				buildB(c, bestClose[c])
			}
		}
		return
	}

	h := bestChild[v][s]
	for _, c := range children[v] {
		if c == h {
			buildB(c, s-1)
		} else {
			join := INF
			if s+1 <= maxD {
				join = A[c][s+1]
			}
			if join <= closeCost[c] {
				buildA(c, s+1, center)
			} else {
				buildB(c, bestClose[c])
			}
		}
	}
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	fmt.Fscan(in, &n, &k)
	maxD = n - 1

	d = make([]int64, n+1)
	for i := 1; i <= maxD; i++ {
		fmt.Fscan(in, &d[i])
	}

	adj = make([][]int, n+1)
	for i := 0; i < n-1; i++ {
		var u, v int
		fmt.Fscan(in, &u, &v)
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	children = make([][]int, n+1)
	A = make([][]int64, n+1)
	B = make([][]int64, n+1)
	bestChild = make([][]int, n+1)
	closeCost = make([]int64, n+1)
	bestClose = make([]int, n+1)
	centerMem = make([][]int, n+1)
	ans = make([]int, n+1)

	for i := 0; i <= n; i++ {
		A[i] = make([]int64, n+1)
		B[i] = make([]int64, n+1)
		bestChild[i] = make([]int, n+1)
		centerMem[i] = make([]int, n+1)
		for j := 0; j <= n; j++ {
			A[i][j] = INF
			B[i][j] = INF
			bestChild[i][j] = -1
		}
	}

	dfs(1, 0)
	buildB(1, bestClose[1])

	fmt.Fprintln(out, closeCost[1])
	for i := 1; i <= n; i++ {
		if i > 1 {
			fmt.Fprint(out, " ")
		}
		fmt.Fprint(out, ans[i])
	}
	fmt.Fprintln(out)
}