There are $$$n$$$ cities in Dadorlandtiria, numbered from $$$0$$$ to $$$n-1$$$. The country is connected with $$$n-1$$$ roads, where the $$$i$$$-th road connects cities $$$u[i]$$$ and $$$v[i]$$$. It costs $$$w[i]$$$ dadorian dollars to cross the $$$i$$$-th road. Each pair of cities is reachable from each other using these roads.
A company called "Work Alone" has to finish $$$q$$$ projects. Let's say for some project, $$$m$$$ workers are involved in it, where $$$m$$$ is an even number. The $$$i$$$-th worker lives in the $$$t[i]$$$-th city. For some reason, the CEO of "Work Alone" decided it would be better for workers to work in pairs, so workers should form $$$\frac{m}{2}$$$ pairs and meet in some city. You want to minimize the total cost workers have to pay for transportation.
Find the answer for each project independently.
The first line contains $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$).
The next $$$n-1$$$ lines contain $$$u[i]$$$, $$$v[i]$$$, and $$$w[i]$$$ ($$$0 \le u[i] \lt v[i] \le n - 1$$$, $$$q \le w[i] \le 10^9$$$).
The next $$$q$$$ lines contain $$$m$$$, followed by $$$m$$$ integers $$$t[0], t[1], \ldots, t[m-1]$$$ in the same line ($$$2 \le m \le 5 \cdot 10^5, 0 \le t[i] \le n-1$$$, all values of $$$t$$$ are distinct).
It is guaranteed that the total sum of $$$m$$$ among all projects does not exceed $$$5 \cdot 10^5$$$.
For each project query, print the minimum total cost of transportation.
| Group | Add. constraints | Points |
| $$$0$$$ | examples | $$$0$$$ |
| $$$1$$$ | $$$u[i]=i$$$ and $$$v[i]=i+1$$$ | $$$5$$$ |
| $$$2$$$ | $$$m \le 6, q \le 5 \cdot 10^4$$$ | $$$11$$$ |
| $$$3$$$ | $$$n \le 100$$$ | $$$15$$$ |
| $$$4$$$ | $$$n \le 1000$$$ | $$$15$$$ |
| $$$5$$$ | $$$q = 1, m = n$$$ | $$$21$$$ |
| $$$6$$$ | — | $$$33$$$ |
8 2 4 5 2 2 5 3 2 7 1 3 5 1 0 6 4 1 5 2 1 6 3 4 1 4 0 7 2 4 5
13 2
Dadorlandtiria In the first project, $$$m=4$$$ and $$$t=[1, 4, 0, 7]$$$.
- The first pair can be $$$(7, 4)$$$. If they meet at the $$$5$$$-th city, they spend $$$4+2=6$$$ dadorian dollars to reach city $$$5$$$.
- The second pair is $$$(1, 0)$$$. They can meet at the $$$6$$$-th city, spending $$$3+4=7$$$ dadorian dollars.
In the second project, $$$m=2$$$ and $$$t=[4, 5]$$$. $$$(4, 5)$$$ is the only pair, and they can meet at the $$$5$$$-th city for a total of $$$2+0=2$$$ dadorian dollars.
