给定一个具有 $$$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$$$ — 找到的循环中的顶点数。
在下一行,输出从 $$$1$$$ 到 $$$n$$$ 的 $$$k$$$ 数字——按遍历顺序循环的顶点。
请注意,答案始终存在,因为在给定的约束下,图中始终至少存在一个简单循环。
示例
输入 #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
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