CF1624G.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.

最近，弗拉德沉迷于生成树，因此他的朋友们毫不犹豫地送给他一个包含 $n$ 个顶点和 $m$ 条边的连通带权无向图作为生日礼物。

弗拉德将一棵生成树的“或值”（ority）定义为该生成树中所有边权值的按位或，现在他想知道：通过选择某棵生成树，所能达到的最小可能的或值是多少？生成树是给定图的一个连通子图，且不包含环。

换言之，你需要保留恰好 $n-1$ 条边，使得图保持连通，并使这些边权值的按位或结果尽可能小。你需找出这个最小的按位或值本身。

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.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示输入中测试用例的数量。

每个测试用例前均有一空行。

接下来是两个数 $n$ 和 $m$（$3 \le n \le 2 \cdot 10^5$，$n - 1 \le m \le 2 \cdot 10^5$）—— 分别表示图的顶点数和边数。

随后的 $m$ 行描述了各条边。第 $i$ 行包含三个数 $v_i$、$u_i$ 和 $w_i$（$1 \le v_i, u_i \le n$，$1 \le w_i \le 10^9$，$v_i \neq u_i$）—— 分别表示该边所连接的两个顶点及其权重。

保证所有测试用例的 $m$ 之和与 $n$ 之和均不超过 $2 \cdot 10^5$，且每个测试用例中的图均为连通图。

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

输出 $t$ 行，每行包含对应输入数据组的答案——最小可能的生成树“ority”。

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.

第一个测试用例中的图。

该树的“ority”值为 $2$，即 $2 = 2$，且该值是最小的。

若不删除权值为 $1$ 的边，则“ority”值为 $1\ \text{or}\ 2 = 3$。