7596: Distance

You are given a tree with n nodes, each edge of the tree has a weight, the nodes of the tree are numbered from 1 to n .

Let dist(i,j) be the sum of edges' weight on the path between i and j .

You need to answer m queries, each query is given l,r , you are asked to output the sum of all dist(i,j) , that satisfies l≤i<j≤r .

The input contains several test cases, and the first line contains a single integer T , the number of test cases.

For each test case:

The first line contains two integers n,m .

For the following n−1 lines, each line contains three integers u,v,d , which means that there is an edge between u,v , the weight of this edge is d .

For the following m lines, each line contains two integers l,r , which means that there is a query for l,r .

1≤T≤3 ，1≤n,m,d≤2⋅105 , l≤r , all input are integers.

For each test case, output m lines representing the answer for the given m queries.

You need to output the answer module 232 .