For a tree, we define its values as max{i × ci}, where ci 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 × 3, 6 × 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.
输入格式
The first line contains one integer T(1 ≤ T ≤ 500), representing the number of test cases. For each test case, the first line contains two integers n, m (1 ≤ n, m ≤ 500). The following m lines, each line contains three integer u, v, w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 109), 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 ≥ 50 or m ≥ 50 will not exceed 50.
输出格式
For each test case, output one integer, representing the minimal value of a spanning tree.