Minimum Pairwise Distance on Tree Queries

You are given an unrooted tree with n nodes and weighted edges. The nodes are numbered from 1 to n. The distance between two nodes i and j is defined as the sum of the edge weights on the unique path connecting them, i.e., $$\texttt{dist(i,j)}$$.

You will be given q queries. For each query, two integers l and r are provided, and you are required to compute the minimum distance among all pairs of nodes (i, j) such that \(l \le i < j \le r\). In other words, you need to calculate

Please note that the path between any two nodes may pass through nodes that are not in the range [l, r].

inputFormat

The input begins with a line containing two integers n and q, representing the number of nodes in the tree and the number of queries respectively.

The next n-1 lines each contain three integers u, v, and w, denoting an edge between nodes u and v with weight w.

This is followed by q lines, each containing two integers l and r describing a query.

outputFormat

For each query, output a single integer indicating the minimum distance between any two nodes i and j satisfying \(l \le i < j \le r\).

sample

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

3
2