Givet ett träd med $N$ noder och $N - 1$ kanter, där varje kant $i$ har en komplexitetsnivå $l_i$. Avståndet $d(u, v)$ mellan två noder $u$ och $v$ är summan av komplexitetsnivåerna längs den unika vägen mellan dem i trädet. Observera att $d(u, v) = d(v, u)$ och $d(v, v) = 0$.

Det finns $M$ pussel, och varje pussel $i$ kräver $k_i$ informationsbitar, vilka är placerade längs specifika kanter i trädet. Det är möjligt för flera informationsbitar att finnas på samma kant!

För två godtyckliga noder $S$ och $T$ är en resa mellan $S$ och $T$ framgångsrik om alla nödvändiga informationsbitar för varje pussel som påträffas längs vägen från $S$ till $T$ samlas in. Mer specifikt betraktas ett pussel som lösbart under en resa om alla nödvändiga informationsbitar för det pusslet påträffas längs vägen.

Uppgiften är att beräkna summan av avstånden för alla framgångsrika resor mellan två godtyckliga noder $S$ och $T$ (där $1 \le S \le T \le N$), modulo $10^9 + 7$.

Formellt är uppgiften att beräkna:

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

Med start från en nod $S$ behöver du resa till en annan nod $T$ längs den unika vägen i trädet. Längs vägen kommer varje informationsbit som finns på kanterna av denna väg automatiskt att samlas in. För att resan från $S$ till $T$ ska betraktas som framgångsrik måste den uppfylla följande villkor:

• Låt $O$ vara mängden av pussel för vilka minst en informationsbit har samlats in under resan. Resan är framgångsrik om och endast om alla informationsbitar som krävs för att lösa varje pussel i mängden $O$ har samlats in. Med andra ord måste du ha samlat in varje informationsbit som behövs för att fullständigt lösa varje pussel i $O$.

Indata

Den första raden innehåller två blankstegsavgränsade heltal $N$ och $M$ ($2 \le N \le 10^6, 1 \le M \le 10^6$).

Därefter följer $N - 1$ rader som var och en innehåller tre blankstegsavgränsade heltal $a_i, b_i, l_i$ ($1 \le a_i, b_i \le N, 1 \le l_i \le 10^9$), vilka beskriver en kant $i$ som förbinder noderna $a_i$ och $b_i$ med komplexitet $l_i$.

Sedan följer definitionerna av $M$ pussel. För varje pussel $i$ består indata av en rad som innehåller $k_i$ följt av $k_i$ blankstegsavgränsade heltal $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$), där $u_{i_j}$ är indexen för de kanter på vilka informationsbitarna som krävs för att lösa pusslet finns.

Här är $K$ summan av alla $k_i$-värden över alla pussel, och det garanteras att $1 \le K \le 10^6$.

Utdata

Skriv ut en rad som innehåller ett heltal, svaret på problemet modulo $10^9 + 7$.

Exempel

Exempelindata 1

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

Exempelutdata 1

17

Notering

Figur 1. Trädets struktur. Rutorna är informationsbitarna och värdena på kanterna är komplexiteterna.