Se da un árbol con $N$ nodos y $N - 1$ aristas, donde cada arista $i$ tiene un nivel de complejidad $l_i$. La distancia $d(u, v)$ entre dos nodos $u$ y $v$ es la suma de los niveles de complejidad a lo largo del único camino entre ellos en el árbol. Ten en cuenta que $d(u, v) = d(v, u)$ y $d(v, v) = 0$.

Hay $M$ rompecabezas, y cada rompecabezas $i$ requiere $k_i$ piezas de información, las cuales están ubicadas a lo largo de aristas específicas en el árbol. ¡Es posible que haya múltiples piezas de información en la misma arista!

Para cualesquiera dos nodos $S$ y $T$, un viaje entre $S$ y $T$ es exitoso si, a lo largo del camino de $S$ a $T$, se recolectan todas las piezas de información necesarias para cualquier rompecabezas encontrado. Específicamente, un rompecabezas se considera resoluble durante un viaje si todas las piezas de información requeridas para ese rompecabezas se encuentran a lo largo del camino.

La tarea consiste en calcular la suma de las distancias para todos los viajes exitosos entre cualesquiera dos nodos $S$ y $T$ (donde $1 \le S \le T \le N$), módulo $10^9 + 7$.

Formalmente, la tarea consiste en calcular:

$$\sum_{\substack{1 \le S \le T \le N, \\ \text{journey } (S, T) \text{ is successful}}} d(S, T)$$

Comenzando desde un nodo $S$, debes viajar a otro nodo $T$ a lo largo del único camino en el árbol. En el camino, cualquier pieza de información ubicada en las aristas de este camino se recolectará automáticamente. Para que el viaje de $S$ a $T$ se considere exitoso, debe cumplir la siguiente condición:

• Sea $O$ el conjunto de rompecabezas para los cuales se ha recolectado al menos una pieza de información durante el viaje. El viaje es exitoso si y solo si se han recolectado todas las piezas de información necesarias para resolver cada rompecabezas en el conjunto $O$. En otras palabras, debes haber reunido cada pieza de información necesaria para resolver por completo cada rompecabezas en $O$.

Entrada

La primera línea contiene dos enteros separados por espacios $N$ y $M$ ($2 \le N \le 10^6, 1 \le M \le 10^6$).

Luego siguen $N - 1$ líneas, cada una con tres enteros separados por espacios $a_i, b_i, l_i$ ($1 \le a_i, b_i \le N, 1 \le l_i \le 10^9$), que describen una arista $i$ que conecta los nodos $a_i$ y $b_i$ con complejidad $l_i$.

Luego siguen las definiciones de los $M$ rompecabezas. Para cada rompecabezas $i$, la entrada consta de una línea que contiene $k_i$ seguido de $k_i$ enteros separados por espacios $u_{i_1}, u_{i_2}, \dots, u_{i_{k_i}}$ ($0 \le k_i \le K, 1 \le u_{i_j} \le N - 1$), donde $u_{i_j}$ son los índices de las aristas en las que se encuentran las piezas de información necesarias para resolver el rompecabezas.

Aquí, $K$ es la suma de todos los valores $k_i$ en todos los rompecabezas, y se garantiza que $1 \le K \le 10^6$.

Salida

Imprime una línea con un entero, la respuesta al problema módulo $10^9 + 7$.

Ejemplo

Entrada de ejemplo 1

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

Salida de ejemplo 1

17

Nota

Figura 1. La estructura del árbol. Los rombos son las piezas de información y los valores en las aristas son las complejidades.