Pangaea 1

At the beginning the world had $n$ cities and $n-1$ roads joining them. The cities carry the integer numbers $0$ through $n-1$. Every road can be walked in both directions and joins two different cities. Starting from any city you could reach every other city by walking along one or more roads.

Humans grew wise and built a bright civilization, but laying a new road between two cities was the one thing they never managed.

The creator watched this and started adding one road between two cities every year. He also wanted to know whether humans were clever enough to use the new roads, so he set them the following puzzle.

Every time one road is added, choose some of the roads laid so far so that all cities are connected to each other, directly or indirectly. Make the sum of the lengths of the chosen roads as small as possible, and report that minimum sum.

You represent humankind, and you have to solve the puzzle.

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 the creator laid $m$, separated by a space.

The next $n-1$ lines describe the world at the beginning. Line $i$ ($1 \le i \le n-1$) among them contains the integers $u_i$, $c_i$ ($0 \le u_i < i$, $0 \le c_i \le 10^7$), separated by a space. This means that city $i$ and city $u_i$ are joined by a road of length $c_i$.

The next $m$ lines give the roads the creator laid, in the order he laid them. Line $j$ ($1 \le j \le m$) among them contains the integers $u_j$, $v_j$, $c_j$ ($0 \le u_j, v_j < n$, $0 \le c_j \le 10^7$), separated by a space. This means that the $j$-th road joins city $u_j$ and city $v_j$ and has length $c_j$. $u_j$ and $v_j$ can be equal, and the road can join two cities that a road already joins.

The limits are $1 \le T \le 10$, $1 \le n \le 2000$, and $1 \le m \le 2000$.

Print one line for each test case. On that line print the XOR of all $m$ minimum sums, one for each added road.