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 $\texttt {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 $\texttt {dist}(i,j)$, that satisfies $l \le i<j \le 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 \le T \le 3$，$1\le n,m,d\le 2\cdot 10^5$, $l \le 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 $2^{32}$.