Given a tree with $$$N$$$ nodes and $$$N-1$$$ edges, where each edge $$$i$$$ has a complexity level $$$l_i$$$. The distance $$$d(u, v)$$$ between two nodes $$$u$$$ and $$$v$$$ is the sum of the complexity levels along the unique path between them in the tree. Note that $$$d(u, v) = d(v, u)$$$ and $$$d(v, v) = 0$$$.
There are $$$M$$$ puzzles, and each puzzle $$$i$$$ requires $$$k_i$$$ pieces of information, which are located along specific edges in the tree. It's possible for multiple pieces of information to be on the same edge!
For any two nodes $$$S$$$ and $$$T$$$, a journey between $$$S$$$ and $$$T$$$ is successful if, along the path from $$$S$$$ to $$$T$$$, all necessary pieces of information for any puzzle encountered are collected. Specifically, a puzzle is considered solvable during a journey if all required pieces of information for that puzzle are encountered along the path.
The task is to compute the sum of distances for all successful journeys between any two nodes $$$S$$$ and $$$T$$$ (where $$$1 \leq S \leq T \leq N$$$), modulo $$$10^9 + 7$$$.
Formally, the task is to calculate: $$$$$$\sum_{\substack{1 \leq S \leq T \leq N, \\ \text{journey } (S, T) \text{ is successful}}} d(S, T)$$$$$$
Starting from a node $$$S$$$, you need to travel to another node $$$T$$$ along the unique path in the tree. Along the way, any piece of information located on the edges of this path will automatically be collected. For the journey from $$$S$$$ to $$$T$$$ to be considered successful, it must meet the following condition:
- Let $$$O$$$ be the set of puzzles for which at least one piece of information has been collected during the journey. The journey is successful if and only if all the pieces of information required to solve every puzzle in the set $$$O$$$ have been collected. In other words, you must have gathered every piece of information needed to completely solve each puzzle in $$$O$$$.
The first line contains two space-separated integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 10^6, 1 \leq M \leq 10^6$$$).
Then, $$$N-1$$$ lines follow, each containing three space-separated integers $$$a_i, b_i, l_i$$$ ($$$1 \leq a_i, b_i \leq N, 1 \leq l_i \leq 10^9$$$), describing an edge $$$i$$$ which connects nodes $$$a_i$$$ and $$$b_i$$$ with complexity $$$l_i$$$.
Then, the definitions of $$$M$$$ puzzles follow. For each puzzle $$$i$$$, the input starts with one line containing $$$k_i$$$ followed by $$$k_i$$$ space-separated integers $$$u_{i_1}, u_{i_2}, \ldots, u_{i_{k_i}}$$$ ($$$0 \leq k_i \leq K, 1 \leq u_{i_j} \leq N-1$$$), where $$$u_i$$$ are the indices of the edges on which the pieces of information required to solve the puzzle are located.
Here, $$$K$$$ is the sum of all $$$k_i$$$ values across all puzzles, and it is guaranteed that $$$1 \leq K \leq 10^6$$$.
Output one line, containing one integer, the answer for the problem modulo $$$10^9 + 7$$$.
5 41 2 31 4 11 5 64 3 22 4 41 102 3 4
17
Figure 1. The structure of the tree. The diamonds are the pieces of information, and the values on the edges are the complexities.
