The King of XORia wants to pave a set of dirt roads to connect all $$$N$$$ cities in his kingdom. There are $$$M$$$ bidirectional dirt roads available, and paving a specific road costs $$$W$$$ gold coins. The goal is to pave a subset of these roads so that people can travel between any two cities, while keeping the total cost as small as possible.
The King's wizard has offered him a magical spell with a power of $$$X$$$. The King can choose exactly one road to cast this spell on. If the spell is cast on a road that originally costs $$$W$$$ coins, its paving cost changes to $$$(W \mathbin{\oplus} X)$$$ coins, where $$$\oplus$$$ represents the bitwise XOR operation.
If the King optimally chooses which road to cast the spell on, what is the minimum possible total cost to connect all the cities?
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.
The first line of each test case contains three integers $$$N$$$, $$$M$$$, and $$$X$$$ ($$$2 \le N \le 2 \cdot 10^5$$$, $$$N-1 \le M \le 2 \cdot 10^5$$$, $$$1 \le X \le 10^9$$$) — the number of cities, the number of roads, and the spell power, respectively. Each of the next $$$M$$$ lines contains three integers $$$u$$$, $$$v$$$, and $$$W$$$ ($$$1 \le u, v \le N$$$, $$$1 \le W \le 10^9$$$), meaning there is a bidirectional dirt road between city $$$u$$$ and city $$$v$$$ that costs $$$W$$$ gold coins to pave.
It is guaranteed that it is possible to travel between any pair of cities using the initial set of dirt roads. Additionally, the sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and the sum of $$$M$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print a single integer — the minimum total gold cost to pave a connected network of roads spanning all cities after performing the magical operation on exactly one road.
1 4 5 2 1 2 5 2 3 6 3 4 7 4 1 8 1 3 9
16
