题目描述

John 有一个农场，包含 $n$ 个牧场，$n-1$ 个桥，构成一棵树，其中 John 住在牧场 $1$。每个桥都有一个权值 $w$，表示桥的危险程度，值越大越危险。John 住在 $1$ 号牧场。

每天奶牛都会在这 $n$ 个牧场吃字符串，晚上 John 会把奶牛们牛圈里赶，但是奶牛们只会往 $1$ 号牧场的方向走，也就是不会从离 $1$ 号牧场近的牧场往远的牧场走。John 设计了 $m$ 个建牛圈的方案，第 $i$ 个方案中有 $k_i(k_i \geq 1)$ 个牛圈，建在编号为 $p_{i,1},p_{i,2},\dots,p_{i,k_i}$ 的牧场。为了方便，John 一定会在 $1$ 号牧场建牛圈。设把 $j$ 号牧场的奶牛赶到牛圈走过的最危险的桥的危险程度为 $s_j$，John 想知道 $\sum_{j=1}^n s_j$ 的最小值。如果奶牛本来就在牛圈里，危险程度为 $0$。

输入格式

第一行一个正整数 $n$。

接下来 $n-1$ 行，每行三个正整数 $x,y,w$，表示有一个连接牧场 $x$ 和牧场 $y$ 的桥，权值为 $w$。

一行一个正整数 $m$。

接下来 $m$ 行，每行第一个数 $k_i$，然后 $k_i$ 个正整数 $p_{i,1},p_{i,2},\dots,p_{i,k_i}$。

输出格式

共 $m$ 行，每行一个正整数，表示询问 $i$ 的答案。

样例 #1

样例输入 #1

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

样例输出 #1

0
1
4
4
5

大样例

link

提示

对于 $100\%$ 的数据，保证 $2 \leq n \leq 10^5,\sum k_i \leq 5 \times 10^5,1 \leq x,y,p_{i,j},w \leq n$