Crusade

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

The world has been swallowed by phonk, rave, and TikTok. The crusader Zenik wants to fix this; with fire and sword, he will burn out the infidels, and everyone else along the way.

Zenik’s land (Zenikovia) is a very centralized country, so all roads can be represented as a tree with vertices in the cities. Zenik will start from the capital of Zenikovia — Zenikivka, which corresponds to vertex \(1\). Zenik needs to visit every city in the country and return to the capital such that Zenik traverses each road at most twice. There are a total of \(n\) cities in the country numbered from \(1\) to \(n\), where \(1\) is the capital.

Each time Zenik enters some city for the first time, he will neutralize all infidels and confiscate their treasures. Since Zenik is also human, albeit a little eccentric — he wants to make his task easier by carrying as little weight as possible. The weight of the confiscated goods at vertex \(i\) is equal to \(a_i\). Zenik’s fatigue is the sum of the weights of the treasures he carries while traversing each road, summed over all roads. Minimize Zenik’s fatigue and output the path that achieves this fatigue. The path must contain \(n\) cities in the order of the first visit to each city. The path must start at vertex \(1\) (the capital).

Input

The first line contains a single integer \(n\).

The next \(n-1\) lines contain two integers each: \(v\) and \(u\) — there is a bidirectional road between cities \(v\) and \(u\).

On the \((n+1)\)-th line, there are \(n\) integers \(a_i\) — the weight of the treasure that Zenik confiscates at vertex \(i\).

Output

In the first line, output a single integer — the minimum fatigue of Zenik.

In the second line, output \(n\) integers — Zenik’s path in the order of the first visit to the city. The path must start at vertex \(1\) (the capital).

Constraints

\(1 \le n \le 10^4\),

\(1 \le a,b \le n\),

\(0 \le A_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 1 3 3 2 3 4 3 5 1 6 6 7 1 1 3 1 1 10 6	111 1 3 2 4 5 6 7

Notes

Zenik’s path in the example:

1 -> 3 -> 2 -> 3 -> 4 -> 3 -> 5 -> 3 -> 1 -> 6 -> 7 -> 6 -> 1

Weights of the treasure he will carry:

1 -> 3 - weight 1

3 -> 2 - weight 4

2 -> 3 - weight 5

3 -> 4 - weight 5

4 -> 3 - weight 6

3 -> 5 - weight 6

5 -> 3 - weight 7

3 -> 1 - weight 7

1 -> 6 - weight 7

6 -> 7 - weight 17

7 -> 6 - weight 23

6 -> 1 - weight 23

1 + 4 + 5 + 5 + 6 + 6 + 7 + 7 + 7 + 17 + 23 + 23 = 111