Мэр Юсландии только что выиграл в лотерею и хочет потратить свои деньги на что-нибудь полезное для города. Например, отремонтировать все дороги.
Юсландия состоит из n перекрёстков, соединённых n - 1 двусторонней дорогой. Известно, что от любого перекрёстка можно добраться до любого другого, используя только данные дороги.
В Юсландии есть только одна компания по ремонту дорог — «РД компани». Офис компании расположен в перекрёстке с номером 1. К сожалению, нельзя просто сказать компании РД, какие дороги дороги нужно отремонтировать. Вместо этого у компании есть m сотрудников, каждый из которых может отремонтировать дороги на некотором конкретном пути. Если заплатить i-му работнику ci монет, то он отремонтирует все дороги на пути от перекрёстка ui до некоторого перекрёстка vi, который находится на пути от ui до перекрёстка 1.
Мэр просит вас нанять такое множество работников, чтобы стоимость ремонта дорог была минимальна. Разрешается, чтобы какая-нибудь дорога была отремонтирована несколько раз.
Если невозможно отремонтировать все дороги, то выведите - 1.
Выходные данные
Если отремонтировать все дороги невозможно, то выведите - 1. В противном случае выведите одно целое число — минимальную стоимость ремонта всех дорог.
Примечание
В первом примере можно выбрать работников с индексами 1, 3, 4 и 5. Некоторые дороги будут отремонтированы больше одного раза. Итоговая стоимость будет равна 2 + 3 + 1 + 2 = 8.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 5
1 2
1 3
3 4
4 5
4 6
2 1 2
3 1 4
4 1 3
5 3 1
6 3 2
|
8
|