MST problem

Problem Description

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

Input

The first line contains one integer $T$($1\le T \le 500$), representing the number of test cases. For each test case, the first line contains two integers $n,m$ ($1\le n,m \le 500$). The following $m$ lines, each line contains three integer $u,v,w$ ($1\le u,v \le n, 1\le w \le 10^9$), represent an edge connecting vertex $u$ and $v$, weights $w$. 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 \ge 50$ or $m \ge 50$ will not exceed $50$.

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）