package main

import (
	"fmt"
)

func main() {
	var n int
	var k int64
	fmt.Scan(&n, &k)

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

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

	dist := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		dist[i] = make([]int, n+1)
		for j := 1; j <= n; j++ {
			dist[i][j] = -1
		}
		dist[i][i] = 0
		q := []int{i}
		for len(q) > 0 {
			curr := q[0]
			q = q[1:]
			for _, nxt := range adj[curr] {
				if dist[i][nxt] == -1 {
					dist[i][nxt] = dist[i][curr] + 1
					q = append(q, nxt)
				}
			}
		}
	}

	parent := make([]int, n+1)
	children := make([][]int, n+1)
	var buildTree func(u, p int)
	buildTree = func(u, p int) {
		parent[u] = p
		for _, v := range adj[u] {
			if v != p {
				children[u] = append(children[u], v)
				buildTree(v, u)
			}
		}
	}
	if n > 0 {
		buildTree(1, 0)
	}

	inSubtree := make([][]bool, n+1)
	for i := 1; i <= n; i++ {
		inSubtree[i] = make([]bool, n+1)
	}
	var checkSubtree func(u, root int)
	checkSubtree = func(u, root int) {
		inSubtree[root][u] = true
		for _, v := range children[u] {
			checkSubtree(v, root)
		}
	}
	for i := 1; i <= n; i++ {
		checkSubtree(i, i)
	}

	postOrder := []int{}
	var getPostOrder func(u int)
	getPostOrder = func(u int) {
		for _, v := range children[u] {
			getPostOrder(v)
		}
		postOrder = append(postOrder, u)
	}
	if n > 0 {
		getPostOrder(1)
	}

	DP := make([][]int64, n+1)
	for i := 1; i <= n; i++ {
		DP[i] = make([]int64, n+1)
	}
	BestVal := make([]int64, n+1)
	BestCenter := make([]int, n+1)

	costFunc := func(u, v int) int64 {
		if u == v {
			return k
		}
		return d[dist[u][v]]
	}

	for _, u := range postOrder {
		for v := 1; v <= n; v++ {
			cost := costFunc(u, v)
			for _, w := range children[u] {
				if inSubtree[w][v] {
					cost += DP[w][v]
				} else {
					if DP[w][v] < BestVal[w] {
						cost += DP[w][v]
					} else {
						cost += BestVal[w]
					}
				}
			}
			DP[u][v] = cost
		}

		best := int64(2e18)
		bestC := -1
		for x := 1; x <= n; x++ {
			if inSubtree[u][x] {
				if DP[u][x] < best {
					best = DP[u][x]
					bestC = x
				}
			}
		}
		BestVal[u] = best
		BestCenter[u] = bestC
	}

	if n == 0 {
		return
	}

	ansCost := BestVal[1]
	ansCenter := make([]int, n+1)

	var reconstruct func(u, v int)
	reconstruct = func(u, v int) {
		ansCenter[u] = v
		for _, w := range children[u] {
			if inSubtree[w][v] {
				reconstruct(w, v)
			} else {
				if DP[w][v] <= BestVal[w] {
					reconstruct(w, v)
				} else {
					reconstruct(w, BestCenter[w])
				}
			}
		}
	}

	reconstruct(1, BestCenter[1])

	fmt.Println(ansCost)
	for i := 1; i <= n; i++ {
		fmt.Printf("%d ", ansCenter[i])
	}
	fmt.Println()
}