Clarke and MST

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 315    Accepted Submission(s): 176
**

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

从大到小按位枚举。因为是&  所以把边集中这个位为1的都拿出来，看这些边能不能构成生成树。具体 看代码。（这里用的并查集判断是不是树，也可以用bfs或dfs判断）

/* ***********************************************
Author :guanjun
Created Time :2016/2/16 19:02:06
File Name :bc72c.cpp
************************************************ */
#include
#include
#include
#include
#include
#include
#include
#include
#include