#P9896. MST problem

    ID: 8118 传统题 18000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700二分图论并查集BFS2023“钉耙编程”中国大学生算法设计超级联赛(9)

MST problem

MST problem

Problem Description

For a tree, we define its values as max⁡{i×ci}\max\lbrace i \times c_{i}\rbrace, where cic_{i} means the number of edges where weights ii. For example, if a tree with edges weight 3,3,3,63,3,3,6, its value equals max⁡(3×3,6×1)=9\max(3 \times 3, 6 \times 1) = 9. You're given a connected graph with nn vertices and mm edges. Try to find a spanning tree with minimal value. Output its value.

Input

The first line contains one integer TT(1≤T≤5001\le T \le 500), representing the number of test cases. For each test case, the first line contains two integers n,mn,m (1≤n,m≤5001\le n,m \le 500). The following mm lines, each line contains three integer u,v,wu,v,w (1≤u,v≤n,1≤w≤1091\le u,v \le n, 1\le w \le 10^9), represent an edge connecting vertex uu and vv, weights ww. It is guaranteed that the graph is connected and contains no self-loops (but may contain multi-edges). The number of test cases where n≥50n \ge 50 or m≥50m \ge 50 will not exceed 5050.

Output

For each test case, output one integer, representing the minimal value of a spanning tree.

Sample Input

3
4 4
1 2 1
2 3 1
3 4 2
4 1 2
5 6
1 2 2
2 3 1
1 5 3
1 2 1
4 5 2
4 3 3
2 2
1 2 10
2 1 1

Sample Output

2
3
1

Source

2023“钉耙编程”中国大学生算法设计超级联赛(9)