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

В последнее время Влад увлёкся остовными деревьями, так что его друзья не долго думая подарили ему на день рождения связный взвешенный неориентированный граф из $$$n$$$ вершин и $$$m$$$ рёбер.

Влад определил орность остовного дерева как побитовое ИЛИ всех его весов и теперь его интересует, какова минимальная возможная орность, которой можно добиться, выбрав некоторое остовное дерево. Остовное дерево — связный подграф данного графа, не содержащий циклов.

Иными словами вы хотите оставить $$$n-1$$$ ребро, так чтобы граф остался связным и побитовое ИЛИ весов рёбер было как можно меньше. Вы должны найти само побитовое ИЛИ.

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

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

Перед каждым набором в тесте записана пустая строка.

Далее следуют два числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 2 \cdot 10^5, n - 1 \le m \le 2 \cdot 10^5$$$) — количество вершин и рёбер графа, соответственно.

Следующие $$$m$$$ строк содержат описание рёбер. Строка $$$i$$$ содержит три числа $$$v_i$$$, $$$u_i$$$ и $$$w_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$1 \le w_i \le 10^9$$$, $$$v_i \neq u_i$$$) — вершины, которые соединяет ребро, и его вес.

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

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

Выведите $$$t$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных — минимальную возможную орность остовного дерева.

Пример
Входные данные
3

3 3
1 2 1
2 3 2
1 3 2

5 7
4 2 7
2 5 8
3 4 2
3 2 1
2 4 2
4 1 2
1 2 2

3 4
1 2 1
2 3 2
1 3 3
3 1 4
Выходные данные
2
10
3
Примечание
Изначальный граф из первого примера.
Орность такого дерева равна 2 or 2 = 2 и является оптимальной.
Оставив ребро веса $$$1$$$ мы получим орность 1 or 2 = 3.