There is a country called Trystland which consists of N cities s.t. there is a unique path between every pair of cities. Adjacent cities are connected by roads of some positive length L. The king of Trystland has plans to reduce the size of country. He wants to keep K special cities of his choice. For these cities to remain connected he needs to keep other cities too. He wants to keep as few cities as possible to keep the special cities connected.
He wants to measure the goodness of the new country formed according to his plan. For measuring goodness, we define a city as junction if there are at-least 3 distinct roads joined to that city. Goodness of a country is defined as sum of distances between every junction city & special city.
The king has Q plans. Can you help him in finding out goodness of country formed according to his plans...
Input
First line of input contains N, the number of cities in Trystland.
N−1 lines follows each containing 3 integers u, v & L denoting that there is a road of length L between city u & v.
Next line contains Q, the number of plans king has.
Q plans follows. First line of each plan contains K(≥1), number of special cities. On next line K space separated integers are there denoting the special cities.
Output
For each plan output a single integer in a newline which is the goodness of the country formed according to the plan.
Constraints
- 1≤N≤1.5∗105
- 1≤u,v≤N
- 1≤L≤107
- ∑K (over all plans) ≤2∗105
In the first plan new country formed consists of all cities. 2 is the only junction city. Hence, goodness is dist(2,1)+dist(2,3)+dist(2,4)=2+1+3=6.
In the second plan new country formed consists of cities 2 3 & 4. There is no junction city. Thus, goodness is 0.
In the third plan note that 2 is a special as well as junction city.
