B"Let's define the Eulerian traversal of a tree (a connected undirected graph without cycles) as follows: consider a depth-first search algorithm which traverses vertices of the tree and enumerates them in the order of visiting (only the first visit of each vertex counts). This function starts from the vertex number 1 and then recursively runs from all vertices which are connected with an edge with the current vertex and are not yet visited in increasing numbers order. Formally, you can describe this function using the following pseudocode: You are given a weighted tree, the vertices of which were enumerated with integers from 1 to n using the algorithm described above. A leaf is a vertex of the tree which is connected with only one other vertex. In the tree given to you, the vertex 1 is not a leaf. The distance between two vertices in the tree is the sum of weights of the edges on the simple path between them. You have to answer q queries of the following type: given integers v , l and r , find the shortest distance from vertex v to one of the leaves with indices from l to r inclusive. The first line contains two integers n and q ( 3 <= q n <= q 500 ,000, 1 <= q q <= q 500 ,000 ) -- the number of vertices in the tree and the number of queries, respectively. The (i - 1) -th of the following n - 1 lines contains two integers p_i and w_i ( 1 <= q p_i < i, 1 <= q w_i <= q 10^9 ), denoting an edge between vertices p_i and i with the weight w_i . It's guaranteed that the given edges form a tree and the vertices are enumerated in the Eulerian traversal order and that the vertex with index 1 is not a leaf. The next q lines describe the queries. Each of them contains three integers v_i , l_i , r_i ( 1 <= q v_i <= q n, 1 <= q l_i <= q r_i <= q n ), describing the parameters of the query. It is guaranteed that t"...