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:
    
    
      
    next_id = 1  
    id = array of length n filled with -1  
    visited = array of length n filled with false  
      
    function dfs(v):  
        visited[v] = true  
        id[v] = next_id  
        next_id += 1  
        for to in neighbors of v in increasing order:  
            if not visited[to]:  
                dfs(to)  
    

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. 

Input

The first line contains two integers n and q (3 ≤ n ≤ 500 000, 1 ≤ 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 ≤ p_i < i, 1 ≤ w_i ≤ 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 ≤ v_i ≤ n, 1 ≤ l_i ≤ r_i ≤ n), describing the parameters of the query. It is guaranteed that there is at least one leaf with index x such that l_i ≤ x ≤ r_i.

Output

Output q integers — the answers for the queries in the order they are given in the input.

Examples

Input


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


Output


3
0
13


Input


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


Output


3000000000
1000000000
2000000000


Input


11 8
1 7
2 1
1 20
1 2
5 6
6 2
6 3
5 1
9 10
9 11
5 1 11
1 1 4
9 4 8
6 1 4
9 7 11
9 10 11
8 1 11
11 4 5


Output


8
8
9
16
9
10
0
34

Note

In the first example, the tree looks like this: 

<image>

In the first query, the nearest leaf for the vertex 1 is vertex 4 with distance 3. In the second query, the nearest leaf for vertex 5 is vertex 5 with distance 0. In the third query the nearest leaf for vertex 4 is vertex 4; however, it is not inside interval [1, 2] of the query. The only leaf in interval [1, 2] is vertex 2 with distance 13 from vertex 4.
/*
Keep solving problems.
*/

import java.util.*;
import java.io.*;

public class CFA {
    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    private static final long MOD = 1000L * 1000L * 1000L + 7;
    private static final int[] dx = {0, -1, 0, 1};
    private static final int[] dy = {1, 0, -1, 0};
    private static final String yes = "Yes";
    private static final String no = "No";

    int n;
    int q;
    List<List<Edge>> graph = new ArrayList<>();
    List<List<Query>> queries = new ArrayList<>();
    int INDEX = 0;
    int[] startIndex;
    int[] endIndex;
    long[] res;
    long[] dist;
    long[] segTree;
    long[] lazy;
    long INF = Long.MAX_VALUE / 10;

    class Edge implements Comparable<Edge> {
        int from;
        int to;
        long weight;
        public Edge(int from, int to, long weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(to, o.to);
        }

        @Override
        public String toString() {
            return from + " " + to + " " + weight;
        }
    }

    class Query {
        int idx;
        int start;
        int end;
        public Query(int idx, int start, int end) {
            this.idx = idx;
            this.start = start;
            this.end = end;
        }
    }

    void build_tree(int node, int nodeStartIndex, int nodeEndIndex) {
        if(nodeStartIndex > nodeEndIndex) return; // Out of range
        if(nodeStartIndex == nodeEndIndex) { // Leaf node
            segTree[node] = isLeaf(nodeStartIndex) ? dist[startIndex[nodeStartIndex]] : INF; // Init value
            return;
        }

        build_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2);
        build_tree(node * 2 + 1, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex);
        segTree[node] = Math.min(segTree[node * 2], segTree[node * 2 + 1]);
    }

    /**
     * Increment elements within range [queryStartIndex, queryEndIndex] with value
     */
    void update_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryStartIndex, int queryEndIndex, long value) {
        if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryEndIndex || nodeEndIndex < queryStartIndex) {
            // Current segment is not within range [i, j]
            return;
        }
        if(nodeStartIndex >= queryStartIndex && nodeEndIndex <= queryEndIndex) {
            // Segment is fully within range
            segTree[node] += value;
            lazy[node] += value;
            return;
        }

        //-------------
        shift(node, nodeStartIndex, nodeEndIndex);
        //-------------
        update_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex, value);
        update_tree(node * 2 + 1, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex, value);
        segTree[node] = Math.min(segTree[node * 2], segTree[node * 2 + 1]);
    }

    /**
     * Query tree to get max element value within range [queryStartIndex, queryEndIndex]
     */
    long query_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryStartIndex, int queryEndIndex) {
        if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryEndIndex || nodeEndIndex < queryStartIndex) {
            // Out of range
            return INF;
        }
        if(nodeStartIndex >= queryStartIndex && nodeEndIndex <= queryEndIndex) {
            // Current segment is totally within range [i, j]
            return segTree[node];
        }

        //-------------
        shift(node, nodeStartIndex, nodeEndIndex);
        //-------------
        long q1 = query_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex);
        long q2 = query_tree(1 + node * 2, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex);
        return Math.min(q1, q2);
    }

    private void shift(int node, int nodeStartIndex, int nodeEndIndex) {
        if(lazy[node] != 0) { // This node needs to be updated
            int mid = (nodeStartIndex + nodeEndIndex) / 2;
            segTree[2 * node] += lazy[node];
            segTree[2 * node + 1] += lazy[node];

            lazy[node * 2] += lazy[node]; // Mark child as lazy
            lazy[node * 2 + 1] += lazy[node]; // Mark child as lazy
            lazy[node] = 0; // Reset it
        }
    }

    void solve() throws IOException {
        n = nextInt();
        q = nextInt();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            int from = nextInt() - 1;
            int to = i + 1;
            int weight = nextInt();
            graph.get(from).add(new Edge(from, to, weight));
            graph.get(to).add(new Edge(to, from, weight));
        }

        startIndex = new int[n];
        endIndex = new int[n];
        dist = new long[n];
        dfs(-1, 0, startIndex, endIndex, 0);
        for (int i = 0; i < n; i++) {
            queries.add(new ArrayList<>());
        }

        for (int i = 0; i < q; i++) {
            int v = nextInt() - 1;
            int l = nextInt() - 1;
            int r = nextInt() - 1;
            queries.get(v).add(new Query(i, l, r));
        }
        res = new long[q];
        segTree = new long[5 * n];
        lazy = new long[5 * n];
        build_tree(1, 0, n - 1);
        dfs(0, -1);

        for (int i = 0; i < q; i++) {
            outln(res[i]);
        }
    }

    void dfs(int cur, int parent) {
        for (Query q : queries.get(cur)) {
            res[q.idx] = query_tree(1, 0, n - 1, q.start, q.end);
        }

        for (Edge nxt : graph.get(cur)) {
            if (nxt.to != parent) {
                update_tree(1, 0, n - 1, 0, n - 1, nxt.weight);
                update_tree(1, 0, n - 1, startIndex[nxt.to], endIndex[nxt.to], (-2) * nxt.weight);

                dfs(nxt.to, cur);

                update_tree(1, 0, n - 1, 0, n - 1, -nxt.weight);
                update_tree(1, 0, n - 1, startIndex[nxt.to], endIndex[nxt.to], 2 * nxt.weight);
            }
        }
    }

    boolean isLeaf(int idx) {
        return idx != 0 && graph.get(idx).size() == 1;
    }

    // Euler's tour:
    void dfs(int parent, int nodeIndex, int[] startIndex, int[] endIndex, long d) {
        startIndex[nodeIndex] = INDEX;
        INDEX++;
        dist[nodeIndex] = d;
        for (Edge nxt : graph.get(nodeIndex)) {
            if (nxt.to != parent) {
                dfs(nodeIndex, nxt.to, startIndex, endIndex, d + nxt.weight);
            }
        }

        endIndex[nodeIndex] = INDEX - 1;
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }
    long gcd(long a, long b) {
        while(a != 0 && b != 0) {
            long c = b;
            b = a % b;
            a = c;
        }
        return a + b;
    }
    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    private void formatPrint(double val) {
        outln(String.format("%.9f%n", val));
    }
    public CFA() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CFA();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}