As you might already know, Ada the Ladybug is a farmer. She grows many fruits and vegetables. She has to take care of them so she builds many roads between them. She also doesn't want to keep unnecessary roads so after building a road she cleans the rest of roads so her road-system doesn't contain any needless cycles. Each road has some maintenance cost and she always keeps roads in such ways that the total cost is minimized.

Input

The first line of input contains 1 ≤ N ≤ 2*10⁵, 0 ≤ M ≤ 5*10⁵, the number of vegetables and the number of roads built by Ada.

The next M lines contains three integers a, b, c: 0 ≤ a, b < N, 0 ≤ c ≤ 10⁹, a ≠ b, the vegetables connected by road and its maintenance cost.

To simulate the "real-time", a, b, c will be on input as a ⊕ l, b ⊕ l, c ⊕ l, where l is the last answer (start as 0) and operation stands for binary XOR.

Output

For each new road print the number actual best sum of maintenance costs.

Example Input

5 5
4 3 6
6 7 4
8 9 10
8 12 9
8 10 11

Example Output

6
8
8
9
5

Real queries

REAL QUERY: 4 3 6
REAL QUERY: 0 1 2
REAL QUERY: 0 1 2
REAL QUERY: 0 4 1
REAL QUERY: 1 3 2

Example Input 2

6 9
3 2 7
4 5 13
2 6 3
11 10 14
17 18 18
16 23 26
19 18 17
18 19 21
14 13 12

Example Output 2

7
7
11
16
18
18
16
14
11

Real queries 2

REAL QUERY: 3 2 7
REAL QUERY: 3 2 10
REAL QUERY: 5 1 4
REAL QUERY: 0 1 5
REAL QUERY: 1 2 2
REAL QUERY: 2 5 8
REAL QUERY: 1 0 3
REAL QUERY: 2 3 5
REAL QUERY: 0 3 2

Example Input 3

3 4
0 1 8
8 10 13
15 13 4
13 12 8

Example Output 3

8
13
13
10

Example Input 4

6 7
4 3 3
3 6 4
14 9 13
8 15 14
11 13 9
17 16 20
13 14 6

Example Output 4

3
10
10
14
21
15
24

Example Input 5

7 11
3 0 997179154
997179152 997179154 204554238
1926119418 1926119416 1370896084
2521188650 2521188654 3204670819
3213587831 3213587825 2592574673
3142795976 3142795983 3067341340
3369331620 3369331617 3266995941
3544021221 3544021220 3341161807
2952422819 2952422823 3068368185
2952422818 2952422823 3137316850
2952422817 2952422819 2934379046

Example Output 5

997179154
1926119422
2521188648
3213587827
3142795978
3369331616
3544021221
2952422819
2952422819
2952422819
2349523846