Butea

Task

You are given a weighted binary tree with $n$ nodes and $q$ queries.

For the $i$-th query ($1 \leq i \leq q$):

• you are given an integer $k_i$ and a set of $k_i$ nodes $S_1, S_2, \dots, S_{k_i}$;
• you must choose another set of exactly $k_i$ nodes $T_1, T_2, \dots, T_{k_i}$;

Note that $T$ can also contain nodes from $S$ (or even $T=S$)

• your goal is to minimize the following value: $\sum_{a=1}^{k_i} \sum_{b=1}^{k_i} \mathrm{dist}(S_a, T_b)$ where $\mathrm{dist}(u,v)$ denotes the length of the shortest path between nodes $u$ and $v$ in the tree.

Input data

The first line contains two integers $n$ and $q$ --- the number of nodes and the number of queries.

The next $n$ - $1$ lines describe the edges of the tree. On the $i$-th of these lines, three integers $u_i$, $v_i$, and $w_i$ are given, indicating that there is an edge between nodes $u_i$ and $v_i$ with weight $w_i$.

The next $q$ lines describe the queries. On the $i$-th of these lines are given:

• an integer $k_i$,
• followed by $k_i$ distinct integers representing the nodes $S_1, S_2, \dots, S_{k_i}$.

The values written on the same line are separated by a single space.

Output data

The output will contain $q$ lines. On line $j$ ($1 \leq j \leq q$) output a single integer --- the minimum possible value of the expression corresponding to the $j$-th query.

Constraints and clarifications

• $1 \leq n, q \leq 2 \cdot 10^5$
• $1 \leq w_i \leq 10$ for all $1 \leq i \leq n$.
• $\sum_{i=1}^{q} k_i \leq 2 \cdot 10^5$.
• $1 \le S_i \le n$ for all queries.
• It is guaranteed that the given edges form a binary tree (i.e. for a suitable choice of the root node each node has at most 2 children).

Example

stdin

10 5
3 4 8
10 9 2
8 1 1
4 10 4
7 1 2
10 5 5
6 8 9
1 3 8
3 2 5
3 8 2 7
5 6 7 8 10 9
4 2 10 9 3
5 6 8 1 9 4
3 2 1 5

stdout

51
306
128
280
103

Explanation

For the first query, picking $T=\{1,8,7\}$ yields a cost of 51:

• From node $1$, the cost is $$\operatorname{dist}(1,7)+\operatorname{dist}(1,8)+\operatorname{dist}(1,2) = 2+1+13 = 16.$$
• From node $8$, the cost is $$\operatorname{dist}(8,7)+\operatorname{dist}(8,8)+\operatorname{dist}(8,2)= 3+0+14 = 17.$$
• From node $7$, the cost is $$\operatorname{dist}(7,7)+\operatorname{dist}(7,8)+\operatorname{dist}(7,2)= 0+3+15 = 18.$$

$16+17+18 = 51$.