E. Разворот ребер
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан ориентированный взвешенный граф на $$$n$$$ вершинах и $$$m$$$ ориентированных ребрах, вес $$$i$$$-го ребра равен $$$w_i$$$ ($$$1 \le i \le m$$$).

Нужно развернуть несколько ребер (изменить их ориентацию на противоположную) в этом графе таким образом, чтобы все вершины графа стали достижимы из какой-то одной. Стоимость таких разворотов равна максимальному весу среди всех развернутых ребер. Если можно обойтись без разворота ребер, стоимость считается равной $$$0$$$.

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

Найдите наименьшую стоимость, необходимую для достижения цели. Если решения нет, выведите $$$-1$$$.

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

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

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

Следующие $$$m$$$ строк каждого набора входных данных содержат по $$$3$$$ числа $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \le u, v \le n$$$, $$$1 \le w \le 10^9$$$), которые задают ребро из $$$u$$$ в $$$v$$$ с весом $$$w$$$. Гарантируется, что никакое ребро не соединяет вершину саму с собой, а также никакая пара ребер не имеют одновременно общее начало и общий конец.

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

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

Для каждого набора входных данных выведите наименьшую необходимую стоимость. Если решения нет, выведите $$$-1$$$.

Пример
Входные данные
4
2 1
1 2 3
5 4
1 2 10
2 3 10
3 1 10
4 5 10
4 5
1 2 10000
2 3 20000
1 3 30000
4 2 500
4 3 20
4 5
1 2 10000
2 3 20000
1 3 30000
4 2 5
4 3 20
Выходные данные
0
-1
20
5
Примечание

В первом наборе входных данных существует ребро из $$$1$$$ в $$$2$$$, так что все вершины уже достижимы из $$$1$$$.

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

В третьем наборе входных данных можно развернуть $$$4$$$-е или $$$5$$$-е ребро. После этого все вершины станут достижимы из вершины $$$1$$$. Для ответа выбирается $$$5$$$-е ребро, поскольку его вес меньше.