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

Обмеження: 2 сек., 256 МіБ

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

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

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

Вхідні дані

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

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

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

Вихідні дані

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

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

Обмеження

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

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

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
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

Примітки

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

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