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 dlen 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$依然没有普及开来。这里的城市通过能够在城市间的道路来往的信使来互相传递消息。在 $Walrusland$，城市间的道路保证信使可以从一座城市到任意另一座城市，而且这些道路是等长的。
北极政府决定实施一项信息改革。几座城市被选中成为区域信息中心。维护一座区域信息中心每年需要花费 $k$个 $fishlar$（这是当地的货币）。假设每座区域信息中心总是能即时获得最新的消息。
每一座不是区域信息中心的城市，都会被安排通过一座区域信息中心来保持信息通达。这样，每年维护费用将会等于 dlen 个 $fishlar$，其中 $len$表示这座城市到它的区域信息中心的距离，即一个人从这座城市到它的区域信息中心需要走过的道路条数。
你的任务是求出实行这项改革的最小开销。

The first line contains two given numbers n and k (1 ≤n≤ 180, 1 ≤k≤ 10⁵).
The second line contains n- 1 integers d_i, numbered starting with 1 (d_i≤d_i+ 1, 0 ≤d_i≤ 10⁵).
Next n- 1 lines contain the pairs of cities connected by a road.

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.

动态规划