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 \le T \le 5)$, the number of test cases.
For each test case, the first line contains two integers $n, m(2 \le n \le 300000, 1 \le m \le 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 \le x, y \le n, 0 \le w \le 10^9)$, 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.
