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

Дан неориентированный взвешенный граф из $$$n$$$ вершин и $$$m$$$ рёбер. Между каждой парой вершин в графе существует не более одного ребра, граф не содержит петель (рёбер из вершины в себя же). Граф не обязательно связный.

Цикл в графе называется простым, если он не проходит через одну и ту же вершину дважды и не содержит одно и то же ребро дважды.

Найдите любой простой цикл этого графа, в котором вес самого лёгкого ребра минимален.

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

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

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

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

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

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

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

Для каждого набора входных данных выведите пару чисел $$$b$$$ и $$$k$$$, где:

  • $$$b$$$ — минимальный вес ребра в найденном цикле,
  • $$$k$$$ — количество вершин в найденном цикле.

В следующей строке выведите $$$k$$$ чисел от $$$1$$$ до $$$n$$$  — вершины цикла в порядке обхода.

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

Пример
Входные данные
5
6 6
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1
6 6
1 2 10
2 3 8
3 1 5
4 5 100
5 6 40
6 4 3
6 15
1 2 4
5 2 8
6 1 7
6 3 10
6 5 1
3 2 8
4 3 4
5 3 6
2 6 6
5 4 5
4 1 3
6 4 5
4 2 1
3 1 7
1 5 5
4 6
2 3 2
1 3 10
1 4 1
3 4 7
2 4 5
1 2 2
4 5
2 1 10
3 1 3
4 2 6
1 4 7
2 3 3
Выходные данные
1 3
1 2 3 
3 3
6 4 5 
1 5
4 2 1 6 3 
1 4
1 4 3 2 
3 3
2 3 1