태초에 세계는 (n)개의 도시와 이들 사이를 잇는 (n - 1)개의 도로로 이루어져 있었다. 각 도시에는 0 이상 (n-1) 이하의 정수 번호가 붙어 있었다. 각 도로는 양방향으로 통행 가능하며, 양 끝에 서로 다른 두 개의 도시를 연결하고 있었다. 태초에 세계는 임의의 도시에서 출발하여 다른 모든 도시로 한 개 이상의 도로를 통하여 걸어갈 수 있었다. </p>

지혜를 갖춘 인간들은 어느새 찬란한 문명을 가지게 되었으나, 도시 사이에 새로운 도로를 놓는 일만큼은 어떻게 해도 해낼 수가 없었다.

이를 지켜보던 조물주는 해마다 두 도시를 잇는 도로를 하나씩 추가하기 시작했는데, 동시에 인간들이 새로운 도로를 사용하기에 합당한 지적 능력을 갖추고 있는지가 궁금해졌다. 그래서 인간들에게 아래와 같은 퍼즐 문제를 제시하였다.

매번 도로가 추가되고 나면 모든 도로 중 일부를 선택하여 모든 도시가 서로 직간접적으로 연결되어 있도록 하며,

이때 선택된 도로들의 길이의 합을 최소로 하는 도로의 부분집합을 알아내기.

조물주에게 문제를 받은 인간들은, 이 문제를 해결하여 조물주에게 자신들이 도로를 사용하기에 합당한 존재라는 것을 보여주기로 하였다. 만약 문제를 해결하지 못한다면, 인간들에게 실망한 조물주가 어떤 일을 일으킬지 아무도 알 수 없다. 당신은 인간계 대표로서, 조물주가 내린 시련을 이겨내야만 한다!

입력 형식

첫 줄에는 테스트 케이스의 수 (T)가 정수로 주어진다. 이어서 매 테스트 케이스의 첫 줄에는 도시의 수 (n)과 도로가 건설된 횟수 (m)이 공백으로 구분되어 주어진다. 다음 (n - 1)줄에 태초의 세계에 대한 정보가 주어진다. 이 중 (i) ((1 \leq i \leq n - 1))번째 줄에는 정수 (u_i, c_i) ((0 \leq u_i < i, 0 \leq c_i \leq 10,000,000))가 공백으로 구분되어 주어지는데, 이는 (i)번 도시와 (u_i)번 도시가 길이가 (c_i)인 도로로 연결되어 있다는 뜻이다. 이어서 (m)개의 줄에 조물주가 새로이 놓은 도로에 대한 정보가 주어진다. 이 중 (j) ((1 \leq j \leq m))번째 줄에는 정수 (u_j, v_j, c_j) ((0 \leq u_j, v_j < n, 0 \leq c_j \leq 10,000,000))가 공백으로 구분되어 주어지는데, 이는 조물주가 (j)번째로 놓은 도로는, (u_j)번 도시와 (v_j)번 도시 사이를 연결하며, 길이가 (c_i)라는 것을 의미한다.</p>

이 문제는 두 개의 부분문제로 이루어져 있다.

1번 문제의 입력은 (1 \leq n, m \leq 2,000)을 만족하며 해결하면 20점을 얻을 수 있다.

2번 문제의 입력은 (1 \leq n, m \leq 100,000)을 만족하며 해결하면 80점을 얻을 수 있다.

출력 형식

각 테스트 케이스마다 단 하나의 줄을 출력한다. 이 줄에는 매번 새 도로를 놓았을 때 문제에 대한 답을 모두 XOR한 값을 출력한다.

예제 입력

1
3 3
0 5
1 3
0 2 4
0 1 2
0 0 2

예제 출력

7