Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Information Reform

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThought 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.

Input

The first line contains two given numbers *n* and *k* (1 ≤ *n* ≤ 180, 1 ≤ *k* ≤ 10^{5}).

The second line contains *n* - 1 integers *d*_{i}, numbered starting with 1 (*d*_{i} ≤ *d*_{i + 1}, 0 ≤ *d*_{i} ≤ 10^{5}).

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

Output

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.

Examples

Input

8 10

2 5 9 11 15 19 20

1 4

1 3

1 7

4 6

2 8

2 3

3 5

Output

38

3 3 3 4 3 4 3 3

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/20/2017 20:25:04 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|