# 3631. Delivery Service

EOJ Delivery Service Company handles a massive amount of orders in our nation. As is well known, our nation has $n$ cities, with $n-1$ bi-directional paths connecting them, forming a tree. The length of the $i$-th path is $w_i$, meaning that the time we have to spend walking through this path is $w_i$.

Now, you, as the headquarter of EOJ, has somehow learned a magic spell. Each time you cast a spell on two paths, the lengths of these two paths magically swap with each other. You can do this magic as many times as you want (possibly none).

We have $q$ orders waiting to be handled. The $i$-th order demands sending a package from city $s_i$ to city $t_i$. We kindly ask you to do your magic before all the deliveries start, such that the total time we have to spend on delivering these packages is minimized.

### 输入格式

The first line of the input contains one single integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The next $n-1$ lines tell about the path information from path $1$ to path $n-1$, the $i$-th of which contains three space-separated integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$, $1 \le w_i \le 1000$).

The next line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$).

The next $q$ lines each contains two space-separated integers $s_i$ and $t_i$ ($1 \le s_i, t_i \le n, s_i \neq t_i$).

### 输出格式

Output one integer, the minimum total time you can achieve.

### 样例

Input
5
1 2 2
1 3 3
3 4 3
3 5 4
2
1 5
4 2

Output
14


### 提示

In the example, we swap the weights between edge $(1,2)$ and $(1,3)$, so that the first order takes $2+4=6$ time units to complete; the second order takes $2+3+3=8$ time units. Thus the total time is $14$.

46 人解决，54 人已尝试。

61 份提交通过，共有 197 份提交。

3.8 EMB 奖励。