Today, your best friends give you a graph G as a birthday present though today is not your birthday. They ask you to nd the minimum spanning tree of G in 3 seconds otherwise they will "pie" your face. You answer that question in just 0.3 seconds since it is too easy for a smart programmer like you.
To hit back, you ask them to nd the maximum spanning tree of G in 3 seconds. But they are almost as smart as you, and answer this question in 0.31 seconds.
One of your best friends, Kirito, is a big fan of bitwise operation. He can solve 14 queens problem in 3 seconds using bitwise operations. Now he is holding a big pie, and asking you to nd the maximum AND spanning tree of G in 3 seconds. That is, you should nd a spanning tree T such that the AND(T) is maximized, where T is the bitwise AND sum of weights of edges in T.
For example, if there are three edges with weights 5, 6, 7 in T, we have AND(T) = 5&6&7 = 1012 &1102 &1112 = 1002 = 4.
The first line of the input data contains an integer T (1 ≤ T ≤ 50) specifying the number of test cases.
Each test case starts with a line contains two integers n;m (2 ≤ n ≤ 50000; n-1 ≤ m ≤ 100000), denoting the number of nodes and edges in the undirected graph G. Each of the following m lines contains three integers ai, bi, ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 109), which means there is an edge (ai, bi) with weight ci in G. We guarantee that G is connected, but there maybe some self-loops and/or multi-edges in G. No more than 5 test cases have max(n,m) > 1000.
For each test case, please output AND(T) of the maximum AND spanning tree T of G.