Pangaea 2

In the beginning the world had $n$ cities and $n - 1$ roads joining them. Each city carries an integer label between $0$ and $n - 1$. Every road can be travelled in both directions and joins two different cities. In that first world you could walk from any city to every other city along one or more roads.

Humans gained wisdom and built a brilliant civilization, yet laying a new road between two cities was the one thing they never managed.

The creator watched this and began laying one road between two cities every year. The creator also wondered whether humans had the intelligence that the new roads deserve, so the creator posed this puzzle.

Every time a road is laid, choose some of the roads laid so far so that all cities are joined to each other directly or indirectly, and make the total length of the chosen roads as small as possible.

The humans who received the puzzle decided to solve it and show the creator that they deserve to use the roads. Nobody knows what a disappointed creator would do if they failed. You represent humankind, so you have to survive the trial the creator set.

The first line contains the number of test cases $T$. The first line of each test case contains the number of cities $n$ and the number of roads laid by the creator $m$, separated by a space ($1 \le n, m \le 100\,000$).

The next $n - 1$ lines describe the first world. Line $i$ ($1 \le i \le n - 1$) contains two integers $u_i, c_i$ ($0 \le u_i < i$, $0 \le c_i \le 10\,000\,000$) separated by a space, which means city $i$ and city $u_i$ are joined by a road of length $c_i$.

The next $m$ lines describe the roads the creator laid, in the order they were laid. Line $j$ ($1 \le j \le m$) contains three integers $u_j, v_j, c_j$ ($0 \le u_j, v_j < n$, $0 \le c_j \le 10\,000\,000$) separated by spaces, which means the $j$-th road the creator laid joins city $u_j$ and city $v_j$ and has length $c_j$. $u_j$ and $v_j$ may be equal, and the road may join two cities that a road already joins.

Print one line for each test case. The line contains the XOR of all $m$ answers, one answer for each road the creator laid.