Хрестовий похід

Limits: 2 sec., 256 MiB

Світ поглинули фонк, рейв і тікток. Хрестоносець Зеник хоче це виправити, вогнем і мечем він випалюватиме невірних, та і всіх інших за компанію.

Земля Зеника (Зениковія) — дуже централізована країна, тому усі дороги можна уявити у вигляді дерева з вершинами в містах. Почне Зеник зі столиці Зениковії — Зениківки, яка відповідає вершині $1$. Зенику потрібно завітати у кожне місто країни і повернутись у столицю так, щоб по кожній дорозі Зеник пройшов не більше двох разів. Усього у країні $n$ міст пронумерованих від $1$ до $n$, де $1$ — столиця.

Кожен раз, коли Зеник вперше заходить в деяке місто, він буде знеживлювати всіх невірних і конфісковувати їх скарби. Оскільки Зеник теж людина, хоч і трошки дивакувата — він хоче облегшити свою справу тягнучи якомога менше ваги. Вага конфіскату в вершині $i$ рівна $a_i$. Втомленість Зеника — це сума ваг скарбів, з якими він проходить певну дорогу, для усіх доріг. Мінімізуйте втомленість Зеника і виведіть шлях при якому можливо досягти такої втомленості. Шлях повинен містити $n$ міст у порядку першого заходу в місто. Шлях повинен починатись у вершині $1$ (столиці).

Input

У першому рядку задано одне ціле число $n$.

У наступних $n-1$ рядках задано по два цілих числа: $v$ і $u$ — існує двостороння дорога між містами $v$ і $u$.

У рядку $n+1$ записано $n$ цілих чисел $a_i$ — вага скарбу, який Зеник конфіскує у вершині $i$.

Output

У першому рядку виведіть одне ціле число — мінімальну втомленість Зеника.

У другому рядку виведіть $n$ цілих чисел — шлях Зеника у порядку першого заходу в місто. Шлях повинен починатись у вершині $1$ (столиці).

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

Шлях Зеника у прикладі:

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

Ваги скарбу що він тягнутиме:

1 -> 3 - вага 1

3 -> 2 - вага 4

2 -> 3 - вага 5

3 -> 4 - вага 5

4 -> 3 - вага 6

3 -> 5 - вага 6

5 -> 3 - вага 7

3 -> 1 - вага 7

1 -> 6 - вага 7

6 -> 7 - вага 17

7 -> 6 - вага 23

6 -> 1 - вага 23

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