说明

时间限制：1 Sec 内存限制：256 MB 输入文件：lucky.in 输出文件：lucky.out

xm 国的小镇有一个传统：从镇上的树中，切出包含 $3$ 个吉利顶点、顶点数尽可能小的子树，作为神木。

给定一棵无向树，一共有 $N$ 个顶点，编号从 $0$ 到 $N-1$，有 $N-1$ 条边。第 $i$ 条边（$0 \le i < N-1$）连接顶点 $u_i$ 和 $v_i$，边权为 $w_i$。

请处理 $Q$ 次询问：

每次给定三个互不相同的顶点 $x,y,z$，求：树的连通子图中，同时包含 $x,y,z$，且顶点数量最小的那个连通子图里所有边的权值之和。

可以证明，满足条件的连通子图是唯一的。

输入格式

第一行一个整数 $N$。

接下来 $N-1$ 行，每行三个整数 $u_i,v_i,w_i$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，每行三个整数 $x_i,y_i,z_i$。

输出格式

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个询问对应的答案。

样例

样例 1

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

3
8
17

样例说明：

第一个询问：顶点数最小的连通子图由顶点 $0,1,2$ 构成。子图内边权总和 $1+2=3$。

第二个询问：连通子图由顶点 $0,1,3,4$ 构成。边权总和 $1+3+4=8$。

第三个询问：连通子图由顶点 $0,1,2,3,5,6$ 构成。边权总和 $1+3+2+5+6=17$。

数据范围

对于 25% 的数据，$N,Q \le 100$。

对于 100% 的数据，$3 \leq N \leq 10^5$，$0 \leq u_i, v_i < N,\ u_i \neq v_i$，边互不重复，$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$ 互不相同。