CF70E.Information Reform

Thought it is already the XXI century, the Mass Media isn't very popular in Walrusland. The cities get news from messengers who can only travel along roads. The network of roads in Walrusland is built so that it is possible to get to any city from any other one in exactly one way, and the roads' lengths are equal.

The North Pole governor decided to carry out an information reform. Several cities were decided to be chosen and made regional centers. Maintaining a region center takes k fishlars (which is a local currency) per year. It is assumed that a regional center always has information on the latest news.

For every city which is not a regional center, it was decided to appoint a regional center which will be responsible for keeping this city informed. In that case the maintenance costs will be equal to d__len fishlars per year, where len is the distance from a city to the corresponding regional center, measured in the number of roads along which one needs to go.

Your task is to minimize the costs to carry out the reform.

尽管如今已是21世纪，但“海象国”（Walrusland）的大众传媒仍不发达。各城市通过信使获取新闻，而信使只能沿道路行进。海象国的道路网络构建得非常特殊：任意两座城市之间都恰好存在唯一一条路径可达，且所有道路的长度均相等。

北极总督决定推行一项信息改革：选定若干城市设立为地区中心。每个地区中心每年的维护费用为 $k$ 鱼拉尔（fishlars，当地货币）。

对于非地区中心的每一座城市，需为其指定一个负责向其传递最新资讯的地区中心；此时，该城市的年维护成本为 $d \cdot \text{len}$ 鱼拉尔，其中 $\text{len}$ 表示该城市到所指定地区中心之间的距离（即二者间路径所含道路的数量）。

你的任务是：最小化此次改革的总成本。

The first line contains two given numbers n and k (1 ≤ n ≤ 180, 1 ≤ k ≤ 105).

The second line contains n - 1 integers d__i, numbered starting with 1 (d__i ≤ d__i + 1, 0 ≤ d__i ≤ 105).

Next n - 1 lines contain the pairs of cities connected by a road.

第一行包含两个给定的数 $n$ 和 $k$（$1 \leq n \leq 180$，$1 \leq k \leq 10^5$）。

第二行包含 $n - 1$ 个整数 $d_i$，下标从 1 开始编号（满足 $d_i \leq d_{i+1}$，且 $0 \leq d_i \leq 10^5$）。

接下来的 $n - 1$ 行每行包含一对由道路连接的城市。

On the first line print the minimum number of fishlars needed for a year's maintenance. On the second line print n numbers, where the i-th number will represent the number of the regional center, appointed to the i-th city. If the i-th city is a regional center itself, then you should print number i.

If there are several solutions to that problem, print any of them.

第一行输出一年维护所需的鱼拉尔（fishlar）最小数量。
第二行输出 $n$ 个数字，其中第 $i$ 个数字表示被指定为第 $i$ 个城市所属区域中心的城市编号。若第 $i$ 个城市本身就是区域中心，则应输出数字 $i$。

若该问题存在多个解，输出任意一个即可。