Minimum OR Spanning Tree

Problem Description

You are given an undirected graph with $n$ vertices and $m$ edges. Each edge connects vertices $u$ and $v$ and has weight $w$. Compute the minimum cost of a spanning tree of the graph.

In this problem, the cost of a spanning tree is defined as the bitwise OR of the weights of all its edges.

Input Format

The first line contains two integers $n$ and $m$, where $n$ is the number of vertices and $m$ is the number of edges.

The next $m$ lines each contain three integers $u, v, w$, indicating an edge of weight $w$ between vertices $u$ and $v$.

Output Format

Output one line containing the minimum cost of a spanning tree.

Sample Input

5 7
4 2 7
2 5 8
3 4 2
3 2 1
2 4 2
4 1 2
1 2 2

Sample Output

10

Constraints

$1 \le u, v \le n \le 2 \times 10^5$, $n-1 \le m \le 4 \times 10^5$, $1 \le w \le 10^9$. At least one spanning tree is guaranteed to exist.