题面描述

给定一张 $n$ 个点，$m$ 条边，边有边权的无向图。定义一个简单环为不经过重复点与重复边的环路径。记一个简单环的权值是环上最小的边权，你需要找到全图中权值最小的一个简单环并输出最小权值。

输入格式

第一行输入一个整数 $t$。代表 $t$ 组询问。

接下来每组数据：

第一行输入两个整数 $n$ 和 $m$ ，表示无向图中点和边的数量。

接下来 $m$ 行每行输入 $3$ 个整数 $u$ , $v$ , 和 $w$，表示编号为 $u$ 和 $v$ 的点由一条边权为 $w$ 的边连接。

数据保证没有重边和自环。注意到如果满足以上约束条件，一定在图中存在一个简单环。

数据保证全部 $t$ 组询问的 $\sum m$ 不超过 $2\times 10^5$。

输出格式

每组数据第一行输出一个整数 $b$，代表简单环边权的最小值,

注意图中至少存在一个简单环。

样例 #1

样例输入 #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
1
3

数据规模与约定

• 对于 $20\%$ 的数据，满足 $1 \leq t\leq 10, 3\leq n \leq m\leq 15$，
• 对于另外 $20\%$ 的数据，满足 $n = m$, 且保证无向图连通，
• 对于另外 $30\%$ 的数据，满足 $1 \leq t\leq 10, 3\leq n \leq m\leq 2000$，
• 对于 $100\%$ 的数据，满足 $ 1 \le t \le 10^4 , 3\leq n\leq m\leq \min\left(2\times 10^5, \frac{n(n-1)}{2}\right), 1 \le u, v \le n,1\leq w\leq 10^6 , u \ne v $。