#P1624G. MinOr Tree

    ID: 1465 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>bitmasksdfs and similardsugraphsgreedy*1900

MinOr Tree

Description

Recently, Vlad has been carried away by spanning trees, so his friends, without hesitation, gave him a connected weighted undirected graph of nn vertices and mm edges for his birthday.

Vlad defined the ority of a spanning tree as the bitwise OR of all its weights, and now he is interested in what is the minimum possible ority that can be achieved by choosing a certain spanning tree. A spanning tree is a connected subgraph of a given graph that does not contain cycles.

In other words, you want to keep n1n-1 edges so that the graph remains connected and the bitwise OR weights of the edges are as small as possible. You have to find the minimum bitwise OR itself.

The first line of the input contains an integer tt (1t1041 \le t \le 10^4) — the number of test cases in the input.

An empty line is written in front of each test case.

This is followed by two numbers nn and mm (3n2105,n1m21053 \le n \le 2 \cdot 10^5, n - 1 \le m \le 2 \cdot 10^5) — the number of vertices and edges of the graph, respectively.

The next mm lines contain the description of the edges. Line ii contains three numbers viv_i, uiu_i and wiw_i (1vi,uin1 \le v_i, u_i \le n, 1wi1091 \le w_i \le 10^9, viuiv_i \neq u_i) — the vertices that the edge connects and its weight.

It is guaranteed that the sum mm and the sum nn over all test cases does not exceed 21052 \cdot 10^5 and each test case contains a connected graph.

Print tt lines, each of which contains the answer to the corresponding set of input data — the minimum possible spanning tree ority.

Input

The first line of the input contains an integer tt (1t1041 \le t \le 10^4) — the number of test cases in the input.

An empty line is written in front of each test case.

This is followed by two numbers nn and mm (3n2105,n1m21053 \le n \le 2 \cdot 10^5, n - 1 \le m \le 2 \cdot 10^5) — the number of vertices and edges of the graph, respectively.

The next mm lines contain the description of the edges. Line ii contains three numbers viv_i, uiu_i and wiw_i (1vi,uin1 \le v_i, u_i \le n, 1wi1091 \le w_i \le 10^9, viuiv_i \neq u_i) — the vertices that the edge connects and its weight.

It is guaranteed that the sum mm and the sum nn over all test cases does not exceed 21052 \cdot 10^5 and each test case contains a connected graph.

Output

Print tt lines, each of which contains the answer to the corresponding set of input data — the minimum possible spanning tree ority.

Sample Input 1

3
<br>
3 3
1 2 1
2 3 2
1 3 2
<br>
5 7
4 2 7
2 5 8
3 4 2
3 2 1
2 4 2
4 1 2
1 2 2
<br>
3 4
1 2 1
2 3 2
1 3 3
3 1 4

Sample Output 1

2
10
3

Note

Graph from the first test case.
Ority of this tree equals to 2 or 2 = 2 and it's minimal.
Without excluding edge with weight 11 ority is 1 or 2 = 3.