MinOr Tree
Recently, Vlad has been carried away by spanning trees, so his friends, without hesitation, gave him a connected weighted undirected graph of $$$n$$$ vertices and $$$m$$$ 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 $$$n-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.
  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 $$$1$$$ ority is 1 or 2 = 3. 
The first line of the input contains an integer $$$t$$$ ($$$1 \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 $$$n$$$ and $$$m$$$ ($$$3 \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 $$$m$$$ lines contain the description of the edges. Line $$$i$$$ contains three numbers $$$v_i$$$, $$$u_i$$$ and $$$w_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$1 \le w_i \le 10^9$$$, $$$v_i \neq u_i$$$) — the vertices that the edge connects and its weight.It is guaranteed that the sum $$$m$$$ and the sum $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ and each test case contains a connected graph.
Print $$$t$$$ lines, each of which contains the answer to the corresponding set of input data — the minimum possible spanning tree ority.
import sys
input = sys.stdin.buffer.readline
uf = None
seq = [None] * 50000

def is_connected(edges, mask):
    for x in range(N):
        uf[x] = x

    def find(x):
        if x == uf[x]:
            return x
        else:
            pos = 0
            seq[pos] = x
            pos += 1
            while uf[x] != x:
                x = uf[x]
                seq[pos] = x
                pos += 1
            for i in range(pos):
                uf[seq[i]] = seq[pos - 1]
            return x
    nc = N
    for (fr, to, w) in edges:
        if not w & mask:
            px = find(fr)
            py = find(to)
            if px != py:
                nc -= 1
            uf[py] = px
    return nc == 1
T = int(input())
for _ in range(T):
    input()
    (N, M) = map(int, input().split())
    uf = list(range(N))
    edges = []
    for _ in range(M):
        (fro, to, weight) = map(int, input().split())
        fro -= 1
        to -= 1
        edges.append((fro, to, weight))
    ANSWER = 0
    FORBIDDEN = 0
    for bit in range(29, -1, -1):
        if is_connected(edges, FORBIDDEN | 1 << bit):
            FORBIDDEN |= 1 << bit
        else:
            ANSWER |= 1 << bit
    print(ANSWER)
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def unionfind(group, root):
    son = root
    while group[root] != root:
        root = group[root]
    while son != root:
        temp = group[son]
        group[son] = root
        son = group[temp]
    return root

def detect(edges, cannot, n):
    group = [i for i in range(n)]
    rest = n - 1
    for [i, j, w] in edges:
        if w & cannot > 0:
            continue
        rooti = unionfind(group, i)
        rootj = unionfind(group, j)
        if rooti == rootj:
            continue
        group[max(rooti, rootj)] = min(rooti, rootj)
        rest -= 1
    if rest == 0:
        output = True
    else:
        output = False
    return output

def main(t):
    s = input()
    (n, m) = map(int, input().split())
    edges = []
    for _ in range(m):
        (u, v, w) = map(int, input().split())
        edges.append([u - 1, v - 1, w])
    cannot = 0
    for d in range(30, -1, -1):
        if detect(edges, cannot + (1 << d), n):
            cannot += 1 << d
    ans = (1 << 31) - 1 - cannot
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1
class UnionFind:

    def __init__(self, n):
        self.par = [-1] * n
        self.rank = [0] * n

    def Find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.Find(self.par[x])
            return self.par[x]

    def Unite(self, x, y):
        x = self.Find(x)
        y = self.Find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x]
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def Same(self, x, y):
        return self.Find(x) == self.Find(y)

    def Size(self, x):
        return -self.par[self.Find(x)]
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
    t = int(input())
    for _ in range(t):
        __ = input()
        (n, m) = map(int, input().split())
        E = []
        for i in range(m):
            (u, v, w) = map(int, input().split())
            (u, v) = (u - 1, v - 1)
            E.append((u, v, w))
        ng = 0
        ans = 0
        for b in reversed(range(30)):
            uf = UnionFind(n)
            for (u, v, w) in E:
                if ng & w != 0:
                    continue
                if 1 << b & w != 0:
                    continue
                uf.Unite(u, v)
            if uf.Size(0) == n:
                ng |= 1 << b
            else:
                ans += 1 << b
        print(ans)
if __name__ == '__main__':
    main()