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.
import java.io.*;
import java.util.*;
import java.awt.Point;

public class CF_1110F {
    static ArrayList<ArrayList<Point>> adj;
    static ArrayList<ArrayList<int[]>> qs;
    static ArrayList<long[]> resps = new ArrayList<>();
    public static void main(String args[]) throws Exception {
        new Thread(null, () -> {
            try {
                BufferedScanner in = new BufferedScanner(System.in);
                BufferedPrinter out = new BufferedPrinter(System.out);

                int n = in.nextInt(), q = in.nextInt();

                adj = get2D(n);
                for (int i = 0; i < n - 1; i++) {
                    int u = i + 1, v = in.nextInt() - 1;
                    int weight = in.nextInt();

                    adj.get(u).add(new Point(v, weight));
                    adj.get(v).add(new Point(u, weight));
                }

                qs = get2D(n);
                for (int i = 0; i < q; i++) {
                    qs.get(in.nextInt() - 1).add(new int[]{in.nextInt() - 1, in.nextInt() - 1, i});
                }

                first = new int[n];
                last = new int[n];
                dists = new long[n];
                init(0, -1, 0);


                LazyST st = new LazyST(n, dists);
                solve(0, -1, 0, st);

                Collections.sort(resps, (a, b) -> Long.compare(a[1], b[1]));
                for (long[] a : resps) out.println(a[0]);

                out.close();
                in.close();
            }catch(Exception e){}
        }, "", 100 * 1000 * 1000).start();
    }

    static int[] first;
    static int[] last;
    static long[] dists;
    static int cnt;
    static void init(int curr, int p, long d){
        if(adj.get(curr).size() == 1) dists[cnt] = d;
        else dists[cnt] = Long.MAX_VALUE / 2;

        first[curr] = cnt;
        cnt++;

        for(Point v: adj.get(curr)){
            if(v.x != p) init(v.x, curr, d + v.y);
        }
        last[curr] = cnt - 1;
    }

    static void solve(int curr, int p, long glob, LazyST st) {
        for(int[] q: qs.get(curr)){
            long ans = st.query(q[0], q[1]) + glob;

            resps.add(new long[]{ans, q[2]});
        }

        for(Point v: adj.get(curr)){
            if(v.x != p){
                st.update(first[v.x], last[v.x], -2 * v.y);
                solve(v.x, curr, glob + v.y, st);
                st.update(first[v.x], last[v.x], 2 * v.y);
            }
        }
    }

    static class LazyST {
        static long nullVal = Long.MAX_VALUE;

        long[] tree;
        long[] updates;
        int n;

        LazyST(int n, long[] initArr) {
            n = (int) Math.pow(2, Math.ceil(Math.log(n) / Math.log(2)));

            tree = new long[2 * n - 1];
            updates = new long[tree.length];

            System.arraycopy(initArr, 0, tree, n - 1, initArr.length);
            for(int i = tree.length - 1; i >= 0; i--) recalc(i);

            this.n = n;
        }

        long combine(long a, long b) {
            return Math.min(a, b);
        }

        void apply(int idx, long u){
            updates[idx] += u;
            tree[idx] += u;
        }

        void update(int left, int right, int diff) {
            update(0, 0, n - 1, diff, left, right);
        }

        void processLazy(int idx) {
            if (l(idx) < tree.length) apply(l(idx), updates[idx]);
            if (r(idx) < tree.length) apply(r(idx), updates[idx]);

            updates[idx] = 0;
        }

        public void update(int idx, int il, int ir, long delta, int ul, int ur) {
            if (ul <= il && ir <= ur) {
                apply(idx, delta);
                return;
            }
            if (il > ur || ir < ul) return;

            processLazy(idx);

            int mid = (il + ir) / 2;
            update(l(idx), il, mid, delta, ul, ur);
            update(r(idx), mid + 1, ir, delta, ul, ur);

            recalc(idx);
        }

        long query(int left, int right) {
            return query(0, left, right, 0, n - 1);
        }

        long query(int idx, int ql, int qr, int il, int ir) {
            if (ql <= il && ir <= qr) return tree[idx];
            if (ql > ir || qr < il) return nullVal;
            processLazy(idx);

            int mid = (il + ir) / 2;
            return combine(query(l(idx), ql, qr, il, mid), query(r(idx), ql, qr, mid + 1, ir));
        }


        public void recalc(int idx) {
            if (l(idx) < tree.length) {
                tree[idx] = tree[l(idx)];
                if (r(idx) < tree.length) {
                    tree[idx] = combine(tree[idx], tree[r(idx)]);
                }
            }
        }

        int p(int n) {
            return (n - 1) / 2;
        }

        int l(int n) {
            return 2 * n + 1;
        }

        int r(int n) {
            return l(n) + 1;
        }

    }

    /**
     * My template below. FastIO and utility functions.
     * Minimized with https://codebeautify.org/javaviewer.
     */

    // @formatter:off
    static<T>ArrayList<ArrayList<T>>get2D(int n){ArrayList<ArrayList<T>>ret=new ArrayList<>();for(int i=0;i<n;i++)ret.add(new ArrayList<>());return ret;}
    static void force(boolean condition){if(!condition)throw new IllegalStateException();}
    static class BufferedPrinter{PrintWriter out;BufferedPrinter(OutputStream out){this(new OutputStreamWriter(out));}
    BufferedPrinter(Writer out){this.out=new PrintWriter(new BufferedWriter(out));}
    void print(Object...os){for(int i=0;i<os.length;i++){if(i!=0)out.print(' ');out.print(os[i]);}}
    void println(Object...os){print(os);out.println();}
    void close(){out.close();}
    void flush(){out.flush();}}
    static class BufferedScanner{private final InputStream in;private final byte[]buf=new byte[1<<13];int pos,count;BufferedScanner(InputStream in)throws IOException{this.in=in;}
    long nextLong()throws IOException{return Long.parseLong(next());}
    int[]nextN(int n)throws IOException{int[]ret=new int[n];for(int i=0;i<n;i++)ret[i]=this.nextInt();return ret;}
    long[]nextNL(int n)throws IOException{long[]ret=new long[n];for(int i=0;i<n;i++)ret[i]=this.nextLong();return ret;}
    private int read(){if(count==-1)err();try{if(pos>=count){pos=0;count=in.read(buf);if(count<=0)return-1;}}catch(IOException e){err();}
    return buf[pos++];}
    private static boolean isSpace(int c){return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;}
    private int readSkipSpace(){int ret;do{ret=read();}while(isSpace(ret));return ret;}
    int nextInt(){int sign=1;int c=readSkipSpace();if(c=='-'){sign=-1;c=read();}
    int ret=0;do{if(c<'0'||c>'9')err();ret=ret*10+c-'0';c=read();}while(!isSpace(c));return sign*ret;}
    String next(){StringBuilder sb=new StringBuilder();int c=readSkipSpace();do{sb.append((char)c);c=read();}while(!isSpace(c));return sb.toString();}
    private void err(){throw new InputMismatchException();}
    void close()throws IOException{in.close();}}
    // @formatter:on
}
