题目描述

在背诵《诗经》的时候，小 G 回忆起了一棵树。树上有 $5$ 个人，他们站在互不相同的节点上。

小 G 想去拜访他们，她会从某个人所在的节点出发，沿树上最短路径走向下一个人，以此类推，直到拜访完这 $5$ 个人。

树上的所有边还未被翻新，翻新一条边需要一定的代价（边是双向的），而小 G 只愿意走被翻新过的边。她想知道，为了使得无论顺序如何都可以拜访完 $5$ 个人，最小需要的翻新代价之和是多少。

输入格式

第一行，一个正整数 $n$，表示节点个数。

接下来 $n − 1$ 行，每行 $3$ 个整数 $u, v, w$，表示 $u$ 和 $v$ 之间有一条边权为 $w$ 的边。点的编号从 $0$ 到 $n − 1$，保证构成的是一棵树。

接下来一行，一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行 $5$ 个正整数 $a, b, c, d, e$，表示 $5$ 个人所在的节点编号，保证它们互不相同。

输出格式

共 $q$ 行，依次对应询问答案。

样例

样例 1

5
0 1 1
1 2 2
2 3 3
3 4 4
1
4 0 3 1 2

10

样例 2

6
4 0 4
0 1 2
1 3 9
3 5 1
3 2 5
2
4 0 3 5 2
0 4 1 3 5

21
16

数据范围

• 子任务 $1$，分值 $7$ 分，保证 $n = 5, q = 1$。
• 子任务 $2$，分值 $23$ 分，保证任意节点度数 $\le 2$。
• 子任务 $3$，分值 $40$ 分，保证 $q \le 100$。
• 子任务 $4$，分值 $30$ 分，无特殊限制。

对于所有数据，$1\le n\le 5\times 10^4$，$1\le q\le 10^4$，$1\le w\le 10^3$。