新加坡全国信息学奥林匹克竞赛（SG NOI）在 2017 年迎来了第 20 届。今年，我们非常荣幸地获得了五（5）家不同的赞助商（按字母顺序排列）：Garena、IMDA、Lee Foundation、Micron，以及主办方兼赞助商：计算学院（SoC）。

SG NOI 组委会主席陈信德（Tan Sun Teck）副教授希望在连接这 5 家赞助商的道路上投放路边广告。他希望确保任何与 SG NOI 相关的人员在他们的办公室之间往返时（例如参加每周重要的 NOI 会议），在他们经过的每一条道路上都能看到与 SG NOI 相关的广告。因此，连接这 5 家赞助商中任意两家的最短路径上的所有道路，都必须安装路边广告。

对于新加坡的每条道路，在该道路上投放广告的成本都是预先确定的。这次广告宣传活动的总成本是这些道路广告成本的总和。陈教授希望找到实现其目标所需的最小成本。

顺便提一下，在这个版本的新加坡中，道路有一个有趣的性质：任意两个地标之间有且仅有一条可行路径（即道路网络是一棵树）。

输入格式

您的程序必须从标准输入中读取。

输入的第一行包含一个正整数 $V$。

接下来的 $V - 1$ 行，每行包含 3 个整数：$u, v, w$，表示新加坡的地标 $u$ 和地标 $v$ 之间有一条道路连接，且在这条道路上安装路边广告的成本为 $w$。

保证 $0 \le u, v < V$ 且 $1 \le w \le 1000$。

接下来的一行包含一个正整数 $Q$，表示询问的数量。

此后的 $Q$ 行，每行包含 5 个整数，表示 SG NOI 的 5 家赞助商所在的地标：地标 $\{a, b, c, d, e\}$。

保证 $a, b, c, d, e$ 两两不同。

图 1：$V = 6$ 的虚拟新加坡样例

输出格式

对于每个询问，您的程序必须向标准输出输出一行，包含一个整数：陈教授路边广告宣传活动的最小成本。

说明

对于第一个询问，5 家赞助商位于地标 $\{4, 0, 3, 5, 2\}$（请注意，地标不一定是排序好的）。为了在这个虚拟的新加坡中连接这 5 家赞助商的所有两两组合，我们需要使用所有的道路。因此，我们需要在每条道路上都放置路边广告。最小成本即为所有道路的成本之和：$4 + 2 + 9 + 1 + 5 = 21$。

对于第二个询问，5 家赞助商位于地标 $\{0, 4, 1, 3, 5\}$。这一次，陈教授可以选择不在道路 $3 - 2$（成本为 5）上放置路边广告（因为地标 2 不是 SG NOI 的赞助商）。因此总成本为 $21 - 5 = 16$。

子任务

每个测试点的最大运行时间为 1.0 秒。您的程序将在以下输入实例集上进行测试：

样例

输入样例 1

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

输出样例 1

10

说明 1

该样例适用于所有子任务。

输入样例 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

输出样例 2

21
16

说明 2

该样例适用于子任务 3 和 4。