판게아 1

태초의 세계는 $n$개의 도시와 이들을 잇는 $n-1$개의 도로로 이루어져 있었다. 도시에는 $0$부터 $n-1$까지 정수 번호가 붙어 있다. 도로는 양방향으로 통행할 수 있고, 서로 다른 두 도시를 연결한다. 어느 도시에서 출발하든 도로를 하나 이상 지나 나머지 모든 도시로 걸어갈 수 있었다.

지혜를 갖춘 인간은 찬란한 문명을 이루었지만, 도시 사이에 새 도로를 놓는 일만은 끝내 해내지 못했다.

이를 지켜보던 조물주는 해마다 두 도시를 잇는 도로를 하나씩 추가하기 시작했다. 그러면서 인간이 새 도로를 쓸 만한 지적 능력을 갖추었는지 궁금해져 다음 퍼즐을 냈다.

도로가 하나 추가될 때마다, 지금까지 놓인 모든 도로 중 일부를 골라 모든 도시가 서로 직접 또는 간접으로 연결되게 한다. 이때 고른 도로의 길이 합이 최소가 되도록 하고, 그 최소 합을 구한다.

인간계 대표인 당신이 이 퍼즐을 풀어야 한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 도시의 수 $n$과 조물주가 도로를 놓은 횟수 $m$이 공백으로 구분되어 주어진다.

이어지는 $n-1$개의 줄에 태초의 세계가 주어진다. 이 중 $i$ ($1 \le i \le n-1$)번째 줄에는 정수 $u_i$, $c_i$ ($0 \le u_i < i$, $0 \le c_i \le 10^7$)가 공백으로 구분되어 주어진다. $i$번 도시와 $u_i$번 도시가 길이 $c_i$인 도로로 연결되어 있다는 뜻이다.

이어지는 $m$개의 줄에는 조물주가 새로 놓은 도로가 놓은 순서대로 주어진다. 이 중 $j$ ($1 \le j \le m$)번째 줄에는 정수 $u_j$, $v_j$, $c_j$ ($0 \le u_j, v_j < n$, $0 \le c_j \le 10^7$)가 공백으로 구분되어 주어진다. $j$번째로 놓인 도로는 $u_j$번 도시와 $v_j$번 도시를 잇고 길이가 $c_j$라는 뜻이다. $u_j$와 $v_j$는 같을 수 있고, 이미 도로가 있는 두 도시를 다시 이을 수도 있다.

$1 \le T \le 10$, $1 \le n \le 2000$, $1 \le m \le 2000$이다.

각 테스트 케이스마다 한 줄을 출력한다. 그 줄에는 도로가 추가될 때마다 구한 최소 길이 합 $m$개를 모두 XOR한 값을 출력한다.