Problem H
Magical Crystals

Photo by cobalt123

There are $n$ cities in the Magical Island, numbered from $1$ to $n$. These cities are connected by $n-1$ bi-directional roads such that there is a unique path between every pair of cities. Each road has a congestion factor. The traffic condition on the Magical Island is very complicated. To transport one magical crystal from city $a$ to city $b$, one must pay a cost that equals the maximum congestion factor among all the roads on the path from city $a$ to city $b$.

Demand and supply of magical crystals vary every year. In the $i$-th year, there are $n_ i$ cities that either generate or request magical crystals. The Magical Island is very aware of energy efficiency, so that every year the demand of magical crystals equals the supply. Each generated magical crystal must be transported to a city that requests magical crystals. The Magical Island needs to arrange the transportation to minimize the transportation cost in each year.

Input

The first line contains a single integer $n$ $(2\leq n\leq 2\cdot 10^5)$. Each of the next $n-1$ lines contains three integers $a, b, w$ $(1\leq a, b\leq n, 0\leq w \leq 10^9)$ that describe a road connecting city $a$ and city $b$ with a congestion factor of $w$. In the next line, there is a single integer $q$ $(1\leq q\leq 2\cdot 10^5)$, the number of years to consider. The input then describes the demand and supply of the $q$ years in order. Each year starts with a positive integer $n_ i$ on the first line. The next $n_ i$ lines each have two integers $x$ ($1 \leq x \leq n$) and $v$ ($v \neq 0$). A positive $v$ means city $x$ generates $v$ magical crystals. A negative $v$ means city $x$ requests $v$ magical crystals. The sum of $v$ in each year is guaranteed to be zero. The total number of magical crystals generated across all $q$ years is no larger than $2\cdot 10^5.$

Output

For each year, output the minimum total cost to transport the magical crystals on a single line.

3
1 2 3
2 3 2
3
2
1 1
2 -1
2
2 1
3 -1
2
1 -2
3 2

3
2
6

6
1 2 6
1 3 8
1 4 4
2 5 12
2 6 2
4
6
1 -5
2 1
3 1
4 1
5 1
6 1
4
3 2
5 -1
6 -2
4 1
2
2 1
6 -1
6
1 1
2 1
3 1
4 -1
5 -1
6 -1

36
26
2
18