Dane jest drzewo o $N$ węzłach i $N - 1$ krawędziach, gdzie każda krawędź $i$ ma poziom złożoności $l_i$. Odległość $d(u, v)$ między dwoma węzłami $u$ i $v$ jest sumą poziomów złożoności wzdłuż jedynej ścieżki między nimi w drzewie. Zauważ, że $d(u, v) = d(v, u)$ oraz $d(v, v) = 0$.

Istnieje $M$ łamigłówek, a każda łamigłówka $i$ wymaga $k_i$ fragmentów informacji, które znajdują się na określonych krawędziach drzewa. Możliwe jest, że na tej samej krawędzi znajduje się wiele fragmentów informacji!

Dla dowolnych dwóch węzłów $S$ i $T$ podróż między $S$ a $T$ jest udana, jeśli wzdłuż ścieżki z $S$ do $T$ zostaną zebrane wszystkie niezbędne fragmenty informacji dla każdej napotkanej łamigłówki. Dokładniej, łamigłówkę uważa się za możliwą do rozwiązania podczas podróży, jeśli wszystkie wymagane fragmenty informacji dla tej łamigłówki zostaną napotkane na ścieżce.

Zadaniem jest obliczenie sumy odległości dla wszystkich udanych podróży między dowolnymi dwoma węzłami $S$ i $T$ (gdzie $1 \le S \le T \le N$), modulo $10^9 + 7$.

Formalnie zadaniem jest obliczenie:

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

Zaczynając od węzła $S$, musisz udać się do innego węzła $T$ wzdłuż jedynej ścieżki w drzewie. Po drodze każdy fragment informacji znajdujący się na krawędziach tej ścieżki zostanie automatycznie zebrany. Aby podróż z $S$ do $T$ została uznana za udaną, musi spełniać następujący warunek:

• Niech $O$ będzie zbiorem łamigłówek, dla których podczas podróży zebrano co najmniej jeden fragment informacji. Podróż jest udana wtedy i tylko wtedy, gdy zebrano wszystkie fragmenty informacji wymagane do rozwiązania każdej łamigłówki ze zbioru $O$. Innymi słowy, musisz zebrać każdy fragment informacji potrzebny do całkowitego rozwiązania każdej łamigłówki w $O$.

Wejście

Pierwszy wiersz zawiera dwie oddzielone spacjami liczby całkowite $N$ oraz $M$ ($2 \le N \le 10^6, 1 \le M \le 10^6$).

Następnie pojawia się $N - 1$ wierszy, z których każdy zawiera trzy oddzielone spacjami liczby całkowite $a_i, b_i, l_i$ ($1 \le a_i, b_i \le N, 1 \le l_i \le 10^9$), opisujące krawędź $i$ łączącą węzły $a_i$ i $b_i$ o złożoności $l_i$.

Następnie podane są definicje $M$ łamigłówek. Dla każdej łamigłówki $i$ wejście składa się z jednego wiersza zawierającego $k_i$, po którym następuje $k_i$ oddzielonych spacjami liczb całkowitych $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$), gdzie $u_{i_j}$ to indeksy krawędzi, na których znajdują się fragmenty informacji wymagane do rozwiązania łamigłówki.

Tutaj $K$ jest sumą wszystkich wartości $k_i$ po wszystkich łamigłówkach i gwarantowane jest, że $1 \le K \le 10^6$.

Wyjście

Wypisz jeden wiersz zawierający jedną liczbę całkowitą — odpowiedź dla zadania modulo $10^9 + 7$.

Przykład

Przykładowe wejście 1

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

Przykładowe wyjście 1

17

Uwaga

Rysunek 1. Struktura drzewa. Romby to fragmenty informacji, a wartości na krawędziach to złożoności.