#P18063. Magical Puzzles

Magical Puzzles

Magical Puzzles

给定一棵有 NN 个顶点、N−1N-1 条边的树。第 ii 条边的权值为 lil_i。令 d(u,v)d(u,v) 表示顶点 u,vu,v 之间唯一路径上所有边权的和,其中 d(v,v)=0d(v,v)=0。

树上有 MM 个谜题。第 ii 个谜题需要 kik_i 条信息,这些信息分别位于指定的边上。多条信息可以位于同一条边上。

从顶点 SS 沿唯一路径前往顶点 TT 时,你会获得沿途每条边上的所有信息。如果对每个谜题,你要么没有获得它的任何信息,要么获得了它的全部信息,就称这次旅程成功。没有任何信息的谜题不会限制旅程。

求所有无序端点对对应的成功旅程的距离和,即

$$\sum_{\substack{1\le S\le T\le N\\(S,T)\text{ 的旅程成功}}}d(S,T),$$

答案对 109+710^9+7 取模。

输入格式

第一行两个整数 N,MN,M。

接下来 N−1N-1 行,第 ii 行三个整数 ai,bi,lia_i,b_i,l_i,表示编号为 ii 的边连接 ai,bia_i,b_i,权值为 lil_i。

接下来 MM 行,第 ii 行先给出整数 kik_i,再给出 kik_i 个整数 ui,1,…,ui,kiu_{i,1},\ldots,u_{i,k_i},表示该谜题各条信息所在的边的编号。这些编号允许重复。

输出格式

输出一个整数,表示答案对 109+710^9+7 取模的结果。

数据范围

2≤N≤1062\le N\le10^6,1≤M≤1061\le M\le10^6,1≤ai,bi≤N1\le a_i,b_i\le N,1≤li≤1091\le l_i\le10^9。

令 K=∑i=1MkiK=\sum_{i=1}^{M}k_i,保证 1≤K≤1061\le K\le10^6,0≤ki≤K0\le k_i\le K,1≤ui,j≤N−11\le u_{i,j}\le N-1。

样例

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