Common Path Edge Weight Sum

Given an unrooted tree with n vertices and weighted edges, let \(E(x,y)\) denote the set of edges along the unique simple path between vertices \(x\) and \(y\) (with \(E(x,x)=\varnothing\)).

You are given q queries. In each query, you are given three integers \(p, l, r\). For each query, determine the sum of weights of the edges in the intersection \[ \bigcap_{i=l}^{r} E(p,i), \] which is equivalent to finding the total weight of the common prefix of the simple paths from \(p\) to every vertex in the set \(\{l, l+1, \ldots, r\}\).

Note that if \(p\) itself lies in the interval \([l,r]\), then one of the queries is \(E(p,p)=\varnothing\) and thus the answer is 0.

inputFormat

The first line contains two integers \(n\) and \(q\) -- the number of vertices and the number of queries.

Each of the next \(n-1\) lines contains three integers \(u, v, w\), meaning there is an undirected edge between vertices \(u\) and \(v\) with weight \(w\).

The following \(q\) lines each contain three integers \(p, l, r\) representing a query.

outputFormat

For each query, output a single integer on a new line -- the sum of the weights of the common edges along the paths from \(p\) to every vertex in \([l, r]\).

sample

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

3
0
0