F. Мобильная сеть
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы руководите мобильным оператором и хотите предлагать конкурентоспособные цены для создания сети.

В сети есть $$$n$$$ узлов.

Ваш конкурент уже предложил некоторые подключения между узлами по некоторым фиксированным ценам. Эти подключения двусторонние. Всего ваш конкурент предложил $$$m$$$ подключений. $$$i$$$-е из этих подключений соединяет узлы $$$fa_i$$$ и $$$fb_i$$$ и стоит $$$fw_i$$$.

У вас есть список из $$$k$$$ подключений, которые вы хотите предложить. Гарантируется, что эти подключения не образуют ни одного цикла. $$$j$$$-е из этих подключений соединит вершины $$$ga_j$$$ и $$$gb_j$$$. Эти подключения тоже двусторонние. Вы еще не определились с ценой каждого из подключений.

Вы можете выбрать стоимости этих подключений любыми целыми числами независимо для каждого из подключений. После этого клиент выберет $$$n - 1$$$ такое подключение из предложенных вами и вашим конкурентом, что все узлы будут объединены в единую сеть, а суммарная стоимость данных подключений будет минимальна. Если существует несколько способов сделать такой выбор, клиент выберет такой, где число ваших подключений максимально.

Вы хотите предложить такие цены, что клиент выберет все $$$k$$$ ваши подключения, а суммарная стоимость этих подключений максимально возможная.

Выведите эту максимально возможную суммарную стоимость, или $$$-1$$$, если она не ограничена.

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

Первая строка содержит три целых числа $$$n$$$, $$$k$$$ и $$$m$$$ ($$$1 \leq n, k, m \leq 5 \cdot 10^5, k \leq n-1$$$) — количество узлов, количество ваших подключений, количество подключений, предложенных конкурентом, соответственно.

Каждая из следующих $$$k$$$ строк содержит два целых числа $$$ga_i$$$ и $$$gb_i$$$ ($$$1 \leq ga_i, gb_i \leq n$$$, $$$ga_i \not= gb_i$$$), описывающее ваше подключение между узлами $$$ga_i$$$ и $$$gb_i$$$. Гарантируется, что эти подключения не образуют цикла.

Следующие $$$m$$$ строк содержат по три целых числа $$$fa_i$$$, $$$fb_i$$$ и $$$fw_i$$$ ($$$1 \leq fa_i, fb_i \leq n$$$, $$$fa_i \not= fb_i$$$, $$$1 \leq fw_i \leq 10^9$$$), описывающие подключение, предложенное конкурентом между узлами $$$fa_i$$$ и $$$fb_i$$$ по цене $$$fw_i$$$. Среди этих подключений нет таких, которые соединяют узел сам с собой, а также нескольких подключений между одной и той же парой узлов. Кроме того, эти подключения заданы в порядке возрастания цены (то есть $$$fw_{i-1} \leq fw_i$$$ для всех $$$i$$$).

Обратите внимание, некоторые подключения могут присутствовать как в вашем списке, так и в списке конкурента (но ни одно не будет присутствовать дважды в одном списке).

Гарантируется, что объединение ваших подключений и подключений конкурента связывает все узлы.

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

Выведите единственное число — максимально возможную прибыль, если вы можете произвольно выбирать стоимости ваших подключений. Если прибыль неограничена, выведите $$$-1$$$.

Примеры
Входные данные
4 3 6
1 2
3 4
1 3
2 3 3
3 1 4
1 2 4
4 2 8
4 3 8
4 1 10
Выходные данные
14
Входные данные
3 2 1
1 2
2 3
1 2 30
Выходные данные
-1
Входные данные
4 3 3
1 2
1 3
1 4
4 1 1000000000
4 2 1000000000
4 3 1000000000
Выходные данные
3000000000
Примечание

В первом примере оптимально дать стоимость $$$3$$$ подключению $$$1-3$$$, стоимость $$$3$$$ подключению $$$1-2$$$, стоимость $$$8$$$ подключению $$$3-4$$$. В таком случае самый дешевый способ получить связную сеть стоит $$$14$$$, и клиент из таких способов выберет тот, которые содержит все ваши подключения.

Во втором примере до тех пор, пока ваше первое подключение стоит $$$30$$$ или меньше, клиент будет вынужден выбрать оба ваших подключения независимо от цены второго, и вы можете получить неограниченную прибыль.