[Sdoi2011]消耗战

战场由 $n$ 个岛屿和 $n-1$ 座桥梁组成，任意两个岛屿之间有且仅有一条路径。敌军总部位于编号为 $1$ 的岛屿。

除 $1$ 号岛屿外，部分岛屿上分布着丰富的能源。为了阻止敌军获取能源，我军需要炸毁一些桥梁，使敌军无法从总部到达任何能源丰富的岛屿。由于桥梁的材质和结构不同，炸毁不同桥梁的代价也不同。请在完成任务的前提下，最小化炸毁桥梁的总代价。

敌军拥有一台神秘机器。每次使用后，这台机器都会修复所有被炸毁的桥梁，并重新随机分布能源，但能源不会出现在 $1$ 号岛屿上。该机器一共可以使用 $m$ 次，你需要分别计算每次能源重新分布后完成任务所需的最小代价。

输入格式

第一行包含一个整数 $n$，表示岛屿数量。

接下来 $n-1$ 行，每行包含三个整数 $u$、$v$、$w$，表示编号为 $u$ 和 $v$ 的岛屿之间有一座桥梁，炸毁该桥梁的代价为 $w$。

第 $n+1$ 行包含一个整数 $m$，表示敌方机器的使用次数。

接下来 $m$ 行，第 $i$ 行首先包含一个整数 $k_i$，表示第 $i$ 次能源重新分布后有 $k_i$ 个岛屿能源丰富；随后包含 $k_i$ 个整数 $h_1,h_2,\ldots,h_{k_i}$，表示这些岛屿的编号。

输出格式

输出 $m$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次任务所需的最小代价。

样例输入

10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6

样例输出

12
32
22

数据范围

• $2\le n\le 250000$；
• $1\le u,v\le n$；
• $1\le w\le 10^5$；
• $m\ge 1$；
• $1\le k_i\le n-1$；
• $\sum k_i\le 500000$。

来源与许可

本题为 SDOI 2011 试题「消耗战」，题面与测试数据整理自 BZOJ。

样例 1

输入

10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6

输出

12
32
22