Багато у світі різних часових поясів! Саме тому змагання з програмування часто бувають у незручний для деяких людей час. Якось Степан та Андрій вирішили взяти участь у змаганні, яке закінчувалося дуже пізно. Саме тому хлопці вирішили переночувати у готелі, щоби не повертатися додому пізно. Але все не так просто. Батьки Андрія та Степана дуже хвилюються за своїх дітей, тож вони вирішили встановити по всьому місту камери, щоб бачити, де знаходяться хлопці.

У місті, де живуть програмісти \(n\) \((1 ≤ n ≤ 500 000)\) перехресть, з'єднаних \(n - 1\) дорогою так, що між будь-якими двома перехрестями існує шлях дорогами.

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

Допоможіть батькам встановити належним чином камери за мінімальну вартість.

Формат вхідних даних

У першому рядку вхідного файлу міститься кількість перехресть \(n\) ( \(1 ≤ n ≤ 500 000\) ).

У наступних \(n -1\) рядках містяться \(v_i\), \(u_i\) - перехрестя з'єднані черговою дорогою.

Останній рядок вхідного файлу містить \(n\) чисел \(сost_1 , сost_2 , ..., сost_n\) (\( 1 ≤ сost_i ≤ 10^9\) ) - вартості установки камер на перехрестях.

Формат вихідних даних

У першому рядку виведіть мінімальну вартість установки \(ans\) і кількість перехресть \(k\) , в яких потрібно встановити камери.

У другому рядку виведіть \(k\) чисел - перехрестя, в яких треба встановити камери. Якщо відповідів декілька, дозволяється вивести будь-яку з них.

Приклад вхідних даних

6
1 2
2 3
1 4
4 5
4 6
228 1488 2 2 8 1

Приклад вихідних даних

232 3
1 3 4