판게아 2

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

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

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

도로가 하나 놓일 때마다, 그때까지 놓인 도로 중 일부를 골라 모든 도시가 서로 직접 또는 간접으로 이어지게 하되, 고른 도로의 길이 합을 최소로 만들어라.

조물주에게 문제를 받은 인간은 이 문제를 풀어 자신들이 도로를 쓰기에 합당한 존재임을 보이기로 했다. 문제를 풀지 못하면 실망한 조물주가 무슨 일을 벌일지 아무도 모른다. 당신은 인간계 대표로서 조물주가 내린 시련을 이겨내야 한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 도시의 수 $n$과 도로가 놓인 횟수 $m$이 공백으로 구분되어 주어진다 ($1 \le n, m \le 100\,000$).

다음 $n - 1$개의 줄에 태초의 세계에 대한 정보가 주어진다. 이 중 $i$ ($1 \le i \le n - 1$)번째 줄에는 정수 $u_i, c_i$ ($0 \le u_i < i$, $0 \le c_i \le 10\,000\,000$)가 공백으로 구분되어 주어진다. 이는 $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\,000\,000$)가 공백으로 구분되어 주어진다. 이는 조물주가 $j$번째로 놓은 도로가 $u_j$번 도시와 $v_j$번 도시를 잇고 길이가 $c_j$라는 뜻이다. $u_j$와 $v_j$는 같을 수도 있고, 이미 도로가 놓인 두 도시를 다시 이을 수도 있다.

각 테스트 케이스마다 한 줄을 출력한다. 이 줄에는 도로를 새로 놓을 때마다 구한 답 $m$개를 모두 XOR한 값을 출력한다.