Anya is playing a spy game! The map that she is currently on is a weighted connected graph with $N$ nodes and $N-1$ edges, where the weight of the $i^{\text{th}}$ edge is $a_i$. It is guaranteed that the graph has no duplicate edges or self-loops.

To conquer the map and move on to the next level, Anya must complete $Q$ levels. The $i^{\text{th}}$ level will consist of exactly $K_i$ nodes, each of which contains an enemy attacker that Anya must take out. Even though Anya is a spy that can take out any opponent, the one thing she cannot do is teleport instantly, so she needs your help to help her calculate some costs.

More specifically, since Anya always wants to be prepared, she wants you to find the maximum cost between two distinct nodes in the level. The cost between two nodes is defined as the minimum number of edges required to travel from one node to the other plus the sum of the costs of the edges on the path. Help Anya find out the answer for each of the queries!

Constraints

$2\le N\le {10}^6$

$1\le Q\le {10}^6$

$1\le a_i\le {10}^9$

$2\le K_i\le N$

The sum of all $K_i$ will not exceed $N$.

Subtask 1 [30%]

$Q=1$

Subtask 2 [69%]

$1\le N,Q\le 150000$

Subtask 3 [1%]

No additional constraints.

Input Specification

The first line of input will contain $N$ and $Q$ separated by a single space. The next $N-1$ lines will each contain three integers $u_i,v_i,a_i$ denoting the two endpoints and the weight of the $i^{\text{th}}$ edge. The final $Q$ lines of input will each contain the integer $K_i$ followed by $K_i$ integers denoting the enemy nodes for the query.

Output Specification

Output $Q$ lines, the $i^{\text{th}}$ of which is the answer to the $i^{\text{th}}$ query.

Sample Input

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

Sample Output

15
10

Explanation

In the first query, the cost of the pair $[5,6]$ is equal to $4+11=15$. This is because the minimum number of roads required to travel from $5$ to $6$ is $4$ and the sum of costs on these roads is equal to $11$. It can be proven that there are no better pairs, so the answer is equal to $15$.

The optimal pairing for the second query is $[1,6]$.