Jamie is gaming instead of focusing on AUCPL Division A again, but he thinks it's fine, as long as he gets a good score. The game is called XOR Racer, and like the name suggests, you win by getting the largest possible XOR score. Every level in this game is defined by a tree, and there are many levels. Each node represents a room, and each edge represents a bidirectional corridor, and thus each level is a separate building.

Each corridor has a certain numerical value, and you can start in any room for each level. Then, you can proceed to walk through the corridors however you like, collecting the different corridor values and XORing them together. For each level, you want to determine the maximum possible value you can obtain. Then, you want to sum these values over the levels to report your total maximum score, so Jamie can win the game.

Thus, Jamie is tasked with calculating the maximum XOR sum of any path in each of the trees representing the levels, and summing them together.

Input

The first line contains two integers ~n~ ~(1 \leq n \leq 2\times 10^5)~ and ~q~ ~(0 \leq q \leq n-1)~, the number of rooms in the entire game and the number of total corridors between them. The rooms are labelled ~1~ to ~n~.

The next ~q~ lines each contain the details of a single undirected corridor. This takes the form of three integers ~u_i~, ~v_i~, and ~c_i~ ~(1\leq u_i,v_i\leq n, 1 \leq c_i \leq 10^9)~, the rooms which the corridor connects and the numerical value assigned to it.

It is guaranteed that the rooms and corridors form a valid forest (that is, collection of trees).

Output

Output a single integer, the sum of the maximum XOR path sum between any two rooms between.

Clarifications

• Trees with a single node contribute ~0~ to the total score, as there are no paths Jamie can take.
• You might need to select pypy3 if you want to use Python to solve this.

Example

Input 1

3 2
1 2 3
2 3 1

Output 1

3

The possible paths are ~1-2~ with path sum ~3~, ~2-3~ with path sum ~1~, and ~1-2-3~ with path sum ~3\oplus 1 = 2~. So the maximum is ~3~, and there is only one tree in this forest.

Input 2

6 4
1 2 5
2 3 6
4 5 1
5 6 2

Output 2

9

In this instance, there are two trees. For the first tree, the possibilities are ~5,6,5\oplus6=3~. We take ~6~. For the second tree the possibilities are ~1,2,1\oplus2=3~, so we take ~3~. Thus the sum is ~9~.