CF1927F Microcycle

给定一个无向带权图，包含 $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 \times 10^5$。

对于每个测试用例，输出一对整数 $b$ 和 $k$，其中： - $b$ 表示找到的环中最小的边权； - $k$ 表示该环的顶点数。 下一行输出 $k$ 个 $1$ 到 $n$ 之间的整数，表示该环的顶点遍历顺序。 注意，答案一定存在，因为在给定的约束下，图中总是至少存在一个简单环。

由 ChatGPT 4.1 翻译