E. Информационная реформа
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Несмотря на то, что уже XXI век на дворе, СМИ в Моржландии не сильно распространены. Оповещение городов ведется с помощью гонцов которые могут путешествовать только по дорогам. Сеть дорог в Моржландии устроена так, что от каждого города до любого другого можно добраться ровно одним способом, и длины дорог равны между собой.

Решением правителя Северного Полюса было принято провести информационную реформу. Было решено выбрать несколько городов и назначить их областными центрами. На обслуживание областного центра приходится тратить k рыбликов (местная валюта) в год. Считается, что областной центр всегда имеет информацию о последних новостях.

Каждому городу, не являющемуся областным центром, было принято решение назначить областной центр, который будет отвечать за информированность этого города. В таком случае затраты на обслуживание равняются dlen рыбликам в год, где len — расстояние от города до соответствующего областного центра, измеряемое в количестве дорог, которые надо проехать.

Ваша задача минимизировать расходы на проведение реформы.

Входные данные

В первой строке заданы два целых числа n и k (1 ≤ n ≤ 180, 1 ≤ k ≤ 105).

Во второй строке записано n - 1 целых чисел di, нумерующихся с единицы (di ≤ di + 1, 0 ≤ di ≤ 105).

В следующих n - 1 строках заданы пары номеров городов соединенных дорогой.

Выходные данные

В первой строке выведите минимальное количество рыбликов, затрачиваемых на обслуживание за один год. Во второй строке выведите n чисел, где i-ое число будет обозначать номер областного центра, который был назначен i-ому городу. Если i-й город сам является областным центром, то следует вывести число i.

Если решений несколько, выведите любое.

Примеры
Входные данные
8 10
2 5 9 11 15 19 20
1 4
1 3
1 7
4 6
2 8
2 3
3 5
Выходные данные
38
3 3 3 4 3 4 3 3