405471: GYM101968 G TeddyBearsDay

You are given the description of TeddyLand, an undirected tree of $$$n$$$ nodes where each node represent a TeddyCity, and there's a TeddyPerson that lives in each of the TeddyCities.

As everyone knows, since the TeddyBearsDay is approaching, people from all around TeddyLand are planning to send TeddyBears to each other.

But we all know that the TeddyDelivery is very expensive these days (the TeddyCost to send a TeddyBear from a TeddyCity to another TeddyCity is the length of the TeddyPath between them!).

So you, the TeddyKing, will rearrange the TeddyDeliveries in such a way that each TeddySender will still send the same amount of TeddyBears, and each TeddyReceiver will still receive the same amount of TeddyBears, and the total TeddyCost is minimum.

The first line will contain one integer $$$T$$$ $$$(1 \le T \le 250)$$$ - the number of TeddyTestCases.

The first line of each TeddyCase will contain one integer $$$n$$$ $$$(1 \le n \le 10000)$$$ - the number of TeddyCities in TeddyLand.

The following $$$n-1$$$ lines will contain three integers each $$$u_{i}$$$ , $$$v_{i}$$$ and $$$w_{i}$$$ $$$(1 \le u_{i}, v_{i} \le n)$$$ $$$(1 \le w_{i} \le 10000)$$$ - meaning that TeddyCity $$$u_{i}$$$ is connected to TeddyCity $$$v_{i}$$$ with a TeddyRoad of length $$$w_{i}$$$.

The next line will contain one integer $$$q$$$ $$$(1 \le q \le 10000)$$$ - the number of TeddyDeliveries planned.

The following $$$q$$$ lines will contain two integers each $$$u_{i}$$$ , $$$v_{i}$$$ $$$(1 \le u_{i}, v_{i} \le n)$$$ - meaning that the TeddyPerson in TeddyCity $$$u_{i}$$$ wants to send a TeddyBear for the TeddyPerson that lives in the TeddyCity $$$v_{i}$$$.

It's possible that $$$u_{i}$$$ is equal to $$$v_{i}$$$.

The total sum of $$$n \le 5*10^5 $$$

The total sum of $$$q \le 5*10^5 $$$

For each test case, output a single line with the minimum total TeddyCost of all TeddyDeliveries after rearrangement.

1
7
1 2 2
2 3 1
2 4 1
1 5 1
5 6 2
5 7 2
2
6 3
4 5

4