CF1927F.Microcycle

Given an undirected weighted graph with $n$ vertices and $m$ edges. There is at most one edge between each pair of vertices in the graph, and the graph does not contain loops (edges from a vertex to itself). The graph is not necessarily connected.

A cycle in the graph is called simple if it doesn't pass through the same vertex twice and doesn't contain the same edge twice.

Find any simple cycle in this graph in which the weight of the lightest edge is minimal.

给定一个包含 $n$ 个顶点和 $m$ 条边的无向带权图。图中任意两个顶点之间至多存在一条边，且图中不含环（即不存在从一个顶点指向其自身的边）。该图不一定是连通的。

若图中某个环不重复经过同一顶点、也不重复经过同一条边，则称其为简单环。

请找出该图中的任意一个简单环，使得其中最轻边的权重最小。

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follow the descriptions of the test cases.

The first line of each test case contains two integers $n$ and $m$ ($3 \le n \le m \le \min(\frac{n\cdot(n - 1)}{2}, 2 \cdot 10^5)$) — the size of the graph and the number of edges.

The next $m$ lines of the test case contain three integers $u$, $v$, and $w$ ($1 \le u, v \le n$, $u \ne v$, $1 \le w \le 10^6$) — vertices $u$ and $v$ are connected by an edge of weight $w$.

It is guaranteed that there is at most one edge between each pair of vertices. Note that under the given constraints, there is always at least one simple cycle in the graph.

It is guaranteed that the sum of the values of $m$ for all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $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$。

For each test case, output a pair of numbers $b$ and $k$, where:

• $b$ — the minimum weight of the edge in the found cycle,
• $k$ — the number of vertices in the found cycle.

On the next line, output $k$ numbers from $1$ to $n$ — the vertices of the cycle in traversal order.

Note that the answer always exists, as under the given constraints, there is always at least one simple cycle in the graph.

对于每个测试用例，输出一对数字 $b$ 和 $k$，其中：

• $b$ —— 所找到环中边的最小权重；
• $k$ —— 所找到环中的顶点数。

在下一行，输出 $k$ 个介于 $1$ 到 $n$ 之间的数字 —— 按遍历顺序排列的环上的顶点。

注意：答案一定存在，因为在给定约束条件下，图中至少存在一个简单环。