D. Дороги в Юсландии
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мэр Юсландии только что выиграл в лотерею и хочет потратить свои деньги на что-нибудь полезное для города. Например, отремонтировать все дороги.

Юсландия состоит из n перекрёстков, соединённых n - 1 двусторонней дорогой. Известно, что от любого перекрёстка можно добраться до любого другого, используя только данные дороги.

В Юсландии есть только одна компания по ремонту дорог — «РД компани». Офис компании расположен в перекрёстке с номером 1. К сожалению, нельзя просто сказать компании РД, какие дороги дороги нужно отремонтировать. Вместо этого у компании есть m сотрудников, каждый из которых может отремонтировать дороги на некотором конкретном пути. Если заплатить i-му работнику ci монет, то он отремонтирует все дороги на пути от перекрёстка ui до некоторого перекрёстка vi, который находится на пути от ui до перекрёстка 1.

Мэр просит вас нанять такое множество работников, чтобы стоимость ремонта дорог была минимальна. Разрешается, чтобы какая-нибудь дорога была отремонтирована несколько раз.

Если невозможно отремонтировать все дороги, то выведите  - 1.

Входные данные

В первой строке входных данных записаны два числа n и m (1 ≤ n, m ≤ 300 000) — количество перекрёстков и количество работников соответственно.

В каждой из следующих n - 1 строк записаны два целых числа xi и yi (1 ≤ xi, yi ≤ n) — индексы перекрёстков, соединённых i-й дорогой.

Последующие m строк описывают работников, которые могут ремонтировать дороги. Каждое описание состоит из трёх целых чисел ui, vi и ci (1 ≤ ui, vi ≤ n, 1 ≤ ci ≤ 109), это означает, что i-й работник может отремонтировать все дороги на пути от ui до vi за ci монет. Гарантируется, что vi лежит на пути между перекрёстком ui и перекрёстком номер 1. Обратите внимание, что ui и vi могут совпадать.

Выходные данные

Если отремонтировать все дороги невозможно, то выведите  - 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
Примечание

В первом примере можно выбрать работников с индексами 1, 3, 4 и 5. Некоторые дороги будут отремонтированы больше одного раза. Итоговая стоимость будет равна 2 + 3 + 1 + 2 = 8.