Problem Description
Clarke is a patient with multiple personality disorder. One day he turned into a learner of graph theory. He learned some algorithms of minimum spanning tree. Then he had a good idea, he wanted to find the maximum spanning tree with bit operation AND. A spanning tree is composed by n−1 edges. Each two points of n points can reach each other. The size of a spanning tree is generated by bit operation AND with values of n−1 edges. Now he wants to figure out the maximum spanning tree.
Input
The first line contains an integer T(1≤T≤5), the number of test cases. For each test case, the first line contains two integers n,m(2≤n≤300000,1≤m≤300000), denoting the number of points and the number of edge respectively. Then m lines followed, each line contains three integers x,y,w(1≤x,y≤n,0≤w≤109), denoting an edge between x,y with value w. The number of test case with n,m>100000 will not exceed 1.
Output
For each test case, print a line contained an integer represented the answer. If there is no any spanning tree, print 0.
Sample Input
1 4 5 1 2 5 1 3 3 1 4 2 2 3 1 3 4 7
Sample Output
1
