Minimum Distance Query on a Weighted Tree

You are given an unrooted weighted tree \(T\) with vertices \(1, 2, \ldots, n\). The tree has \(n-1\) edges. For any two vertices \(i\) and \(j\), we define the distance \(\texttt{dist}(i,j)\) as the sum of weights along the unique simple path connecting \(i\) and \(j\) in \(T\).

You will be given \(q\) queries. For each query, two integers \(l\) and \(r\) are provided. Your task is to compute and output the value of

[ \min_{l \le i < j \le r} \big( \texttt{dist}(i,j) \big). ]

Note: It is guaranteed that \(l < r\), so there is always at least one pair of vertices in the range.

inputFormat

The input is given in the following format:

n q
u1 v1 w1
u2 v2 w2
... (n-1 lines for edges)
 l1 r1
 l2 r2
... (q lines queries)

Where:

• \(n\) is the number of vertices.
• \(q\) is the number of queries.
• Each of the next \(n-1\) lines contains three integers \(u, v, w\) indicating an edge between vertices \(u\) and \(v\) with weight \(w\).
• Each of the following \(q\) lines contains two integers \(l\) and \(r\) for the query.

outputFormat

For each query, output a single integer—the minimum distance among all pairs of distinct vertices \(i, j\) in the range \([l, r]\) (with \(i < j\)). Each answer should be printed on its own line.

sample

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

3
4