Дан неориентированный взвешенный граф из \(n\) вершин и \(m\) рёбер. Между каждой парой вершин в графе существует не более одного ребра, граф не содержит петель (рёбер из вершины в себя же). Граф не обязательно связный.
Цикл в графе называется простым, если он не проходит через одну и ту же вершину дважды и не содержит одно и то же ребро дважды.
Найдите любой простой цикл этого графа, в котором вес самого лёгкого ребра минимален.
Выходные данные
Для каждого набора входных данных выведите пару чисел \(b\) и \(k\), где:
- \(b\) — минимальный вес ребра в найденном цикле,
- \(k\) — количество вершин в найденном цикле.
В следующей строке выведите \(k\) чисел от \(1\) до \(n\) — вершины цикла в порядке обхода.
Обратите внимание, что ответ всегда существует, так как при заданных ограничениях в графе всегда есть хотя бы один простой цикл.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|