311055: CF1927F. Microcycle

F. Microcycletime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

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

Output

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 

题目大意：
给定一个无向加权图，有n个顶点和m条边。图中任意一对顶点之间最多有一条边，且图中不包含自环（即从一个顶点到自身的边）。图不一定是连通的。

如果图中的一个循环不重复经过同一个顶点，并且不重复包含同一条边，则称为简单循环。

在图中找到一个简单循环，使得其中最轻边的权重最小。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数n和m（3≤n≤m≤min(n(n−1)/2, 2×10^5)），分别表示图的顶点数和边数。
- 接下来的m行，每行包含三个整数u、v和w（1≤u,v≤n，u≠v，1≤w≤10^6），表示顶点u和v之间有一条权重为w的边。
- 保证图中任意一对顶点之间最多有一条边。
- 保证所有测试用例的m值之和不超过2×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
```题目大意： 给定一个无向加权图，有n个顶点和m条边。图中任意一对顶点之间最多有一条边，且图中不包含自环（即从一个顶点到自身的边）。图不一定是连通的。 如果图中的一个循环不重复经过同一个顶点，并且不重复包含同一条边，则称为简单循环。 在图中找到一个简单循环，使得其中最轻边的权重最小。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数n和m（3≤n≤m≤min(n(n−1)/2, 2×10^5)），分别表示图的顶点数和边数。 - 接下来的m行，每行包含三个整数u、v和w（1≤u,v≤n，u≠v，1≤w≤10^6），表示顶点u和v之间有一条权重为w的边。 - 保证图中任意一对顶点之间最多有一条边。 - 保证所有测试用例的m值之和不超过2×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 ```