Minimum Risk Path in an Undirected Graph

You are given an undirected graph with \(N\) nodes and \(M\) edges. The graph may contain multiple edges between two nodes and self loops. Each edge has a weight \(w\).

You can choose any two distinct vertices \(start\) and \(end\) in the graph and find a path from \(start\) to \(end\). The risk value of a path is defined as the XOR of the weights of all edges on that path. Note that you are allowed to visit the same vertex or traverse the same edge multiple times.

Your task is to determine the minimum risk value possible over all valid choices of distinct \(start\) and \(end\) vertices and over all paths between them.

Hint: For any connected component, if you choose an arbitrary vertex as the root and compute the XOR distance \(d[u]\) from the root to any vertex \(u\) along a DFS tree, then for any two vertices \(u\) and \(v\) in that component, a candidate risk value is \(d[u]\oplus d[v]\). Moreover, using extra cycles you can further reduce these values. A standard approach is to build an XOR basis from the cycles and then reduce each \(d[u]\) accordingly, after which the answer is the minimum XOR of any two distinct reduced values.

inputFormat

The first line contains two integers \(N\) and \(M\) \((2\le N\le 10^5, 1\le M\le 10^5)\) — the number of vertices and edges.

Each of the following \(M\) lines contains three integers \(u\), \(v\), and \(w\) \((1\le u,v\le N, 0\le w\le 10^9)\), representing an undirected edge between vertices \(u\) and \(v\) with weight \(w\). The graph might contain self loops and multiple edges.

outputFormat

Output a single integer — the minimum risk value achievable by choosing two distinct vertices in the same connected component and a corresponding path between them.

sample

3 3
1 2 1
2 3 2
1 3 3

1