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

Во время долгих экскурсий по Турции Вы видели много разных мозаик, но такой ещё не попадалось вашим глазам!

Мозаика, которую Вы видите, является графом из $$$n$$$ вершин и $$$m$$$ рёбер веса $$$w_i$$$. Вас настолько она впечатлила, что Вы решили поискать тайное послание, которое содержится в ней. Вы перебрали много различных вариантов, и текущее предположение такое: секретное послание — это сумма весов множества из $$$n - 1$$$ рёбер, такое что сумма минимальна и рёбра не образуют дерево.

Для начала Вы хотите узнать это значение, а что оно значит — планируете разобраться во время возвращения домой.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le 2 \cdot 10^5$$$) — число вершин и рёбер в графе, соответственно.

$$$i$$$-я из следующих $$$m$$$ строк содержит три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ ($$$1 \le u_i \ne v_i \le n$$$, $$$1 \le w_i \le 10^9$$$) — описание $$$i$$$-го ребра.

Гарантируется, что граф не содержит петель и кратных рёбер.

Гарантируется, что сумма $$$n$$$ по всем входным данным не превосходит $$$2 \cdot 10^5$$$ и сумма $$$m$$$ по всем входным данным не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите единственное целое число — минимальную сумму весов множества из $$$n - 1$$$ рёбер, не образующего дерево, если такое множество существует. Иначе выведите $$$-1$$$.

Пример
Входные данные
4
4 6
1 2 7
1 3 4
1 4 1
2 3 9
2 4 6
3 4 5
4 4
1 2 5
2 3 5
3 4 5
1 4 8
4 4
1 4 1
1 3 4
2 4 2
3 4 3
4 4
2 3 7
1 2 5
2 4 9
4 3 12
Выходные данные
10
-1
8
28
Примечание

В первом примере можно выбрать второе, третье и шестое ребро, сумма их весов равна $$$4 + 1 + 5 = 10$$$. Можно проверить, что этот набор ребер не образует дерево

Во втором наборе входных данных любое множество из $$$3$$$ ребер образует дерево. Поэтому решения не существует.