Note

Problem Statement

2019/10/4 21:46 The problem statement was corrected.

The town where niuez lives has a certain tradition.
From a tree growing in the town, a piece as small as possible containing $3$ auspicious vertices is cut out and made into a "three-tree offering (mitsugimono)" (tri-butree) to the sacred tree.

There is an undirected tree with $N$ vertices numbered from $0$ to $N-1$ and $N-1$ edges. The $i \ (0 \leq i < N-1)$-th edge has endpoints $u_i$ and $v_i$ and has weight $w_i$.
Process the following $Q$ ${\rm query}$s.

• $x \ y \ z$

  • Among the connected components of the tree, find the total weight of the edges contained in the connected subgraph of the tree that contains the mutually distinct vertices $x, y, z$ and has the minimum number of vertices (2019/10/4 21:44 A terminology error was corrected).
  • It can be proved that such a connected subgraph of the tree is uniquely determined.

Input

$N$
$u_0 \  v_0 \  w_0$
$\cdots$
$u_{N-2} \  v_{N-2} \  w_{N-2}$
$Q$
$x_0 \ y_0 \ z_0$
$\cdots$
$x_{Q-1} \ y_{Q-1} \ z_{Q-1}$

• $3 \leq N \leq 10^5$
• $0 \leq u_i, v_i < N$
  • $u_i \neq v_i$
  • $(u_i, v_i) = (u_j, v_j) \Leftrightarrow i = j$
• $1 \leq w_i < 10^9$
• $1 \leq Q \leq 10^5$
• $0 \leq x_i, y_i, z_i < N$
  • $x_i, y_i, z_i$ are mutually distinct
• All inputs are integers

Output

Output $Q$ lines. On the $i$-th line, output the answer to the $i$-th ${\rm query}$ as an integer.

Sample

Sample 1

Input

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

Output

3
8
17

In the first query, the connected component with the minimum number of vertices is the one consisting of vertices $0, \ 1, \ 2$.
The total weight of the edges contained in that connected component is $1+2=3$.
In the next query, it is the connected component consisting of vertices $0, \ 1, \ 3, \ 4$.
The total weight of the edges contained in it is $1+3+4=8$.
In the third query, it is the connected component consisting of vertices $0, \ 1, \ 2, \ 3, \ 5, \ 6$.
The total weight of the edges contained in it is $1+3+2+5+6=17$.