กำหนดต้นไม้ที่มี $N$ โหนด และ $N - 1$ เส้นเชื่อม โดยที่แต่ละเส้นเชื่อม $i$ มีระดับความซับซ้อน $l_i$ ระยะทาง $d(u, v)$ ระหว่างสองโหนด $u$ และ $v$ คือผลรวมของระดับความซับซ้อนตามเส้นทางหนึ่งเดียวระหว่างโหนดทั้งสองในต้นไม้ สังเกตว่า $d(u, v) = d(v, u)$ และ $d(v, v) = 0$

มีปริศนา $M$ ข้อ และแต่ละปริศนา $i$ ต้องใช้ชิ้นส่วนข้อมูล $k_i$ ชิ้น ซึ่งตั้งอยู่ตามเส้นเชื่อมที่กำหนดในต้นไม้ เป็นไปได้ที่จะมีชิ้นส่วนข้อมูลหลายชิ้นอยู่บนเส้นเชื่อมเดียวกัน!

สำหรับสองโหนด $S$ และ $T$ ใดๆ การเดินทางระหว่าง $S$ และ $T$ จะประสบความสำเร็จหากตามเส้นทางจาก $S$ ไปยัง $T$ ชิ้นส่วนข้อมูลที่จำเป็นทั้งหมดสำหรับปริศนาใดๆ ที่พบถูกเก็บรวบรวมครบถ้วน กล่าวโดยเจาะจงคือ ปริศนาจะถือว่าสามารถไขได้ในระหว่างการเดินทางหากพบชิ้นส่วนข้อมูลที่จำเป็นทั้งหมดสำหรับปริศนานั้นตามเส้นทาง

งานของคุณคือคำนวณผลรวมของระยะทางสำหรับการเดินทางที่ประสบความสำเร็จทั้งหมดระหว่างสองโหนด $S$ และ $T$ ใดๆ (โดยที่ $1 \le S \le T \le N$) มอดูโล $10^9 + 7$

อย่างเป็นทางการ งานของคุณคือการคำนวณ:

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

เริ่มต้นจากโหนด $S$ คุณต้องเดินทางไปยังอีกโหนดหนึ่ง $T$ ตามเส้นทางหนึ่งเดียวในต้นไม้ ระหว่างทาง ชิ้นส่วนข้อมูลใดๆ ที่อยู่บนเส้นเชื่อมของเส้นทางนี้จะถูกเก็บรวบรวมโดยอัตโนมัติ เพื่อให้การเดินทางจาก $S$ ไปยัง $T$ ถือว่าประสบความสำเร็จ จะต้องเป็นไปตามเงื่อนไขต่อไปนี้:

• ให้ $O$ เป็นเซตของปริศนาที่มีการเก็บรวบรวมชิ้นส่วนข้อมูลอย่างน้อยหนึ่งชิ้นในระหว่างการเดินทาง การเดินทางจะประสบความสำเร็จก็ต่อเมื่อชิ้นส่วนข้อมูลทั้งหมดที่จำเป็นในการไขทุกปริศนาในเซต $O$ ถูกเก็บรวบรวมครบแล้ว กล่าวอีกนัยหนึ่ง คุณต้องรวบรวมชิ้นส่วนข้อมูลทุกชิ้นที่จำเป็นเพื่อไขแต่ละปริศนาใน $O$ ให้สมบูรณ์

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัวที่คั่นด้วยช่องว่าง $N$ และ $M$ ($2 \le N \le 10^6, 1 \le M \le 10^6$)

จากนั้นตามด้วย $N - 1$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มสามตัวที่คั่นด้วยช่องว่าง $a_i, b_i, l_i$ ($1 \le a_i, b_i \le N, 1 \le l_i \le 10^9$) อธิบายเส้นเชื่อม $i$ ซึ่งเชื่อมต่อโหนด $a_i$ และ $b_i$ ด้วยความซับซ้อน $l_i$

จากนั้นตามด้วยคำจำกัดความของปริศนา $M$ ข้อ สำหรับแต่ละปริศนา $i$ ข้อมูลนำเข้าเริ่มต้นด้วยหนึ่งบรรทัดที่ประกอบด้วย $k_i$ ตามด้วยจำนวนเต็ม $k_i$ ตัวที่คั่นด้วยช่องว่าง $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$) โดยที่ $u_{i_j}$ คือดัชนีของเส้นเชื่อมซึ่งเป็นที่ตั้งของชิ้นส่วนข้อมูลที่จำเป็นในการไขปริศนา

ในที่นี้ $K$ คือผลรวมของค่า $k_i$ ทั้งหมดจากทุกปริศนา และรับประกันว่า $1 \le K \le 10^6$

ข้อมูลส่งออก

ส่งออกหนึ่งบรรทัด ประกอบด้วยจำนวนเต็มหนึ่งตัว คือคำตอบของปัญหามอดูโล $10^9 + 7$

ตัวอย่าง

ข้อมูลนำเข้า 1

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

ข้อมูลส่งออก 1

17

หมายเหตุ

รูปที่ 1. โครงสร้างของต้นไม้ รูปข้าวหลามตัดคือชิ้นส่วนข้อมูล และค่าบนเส้นเชื่อมคือความซับซ้อน