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.
#include <bits/stdc++.h>
char readCharacter;
bool remaining = false;
template <typename T>
bool readInt(T &x);
template <typename T>
bool readString(T &x);
template <typename T>
bool readChar(T &x);
bool readCharArray(char *&x);
template <typename T>
bool readFloat(T &x);
template <typename T>
bool readDouble(T &x);
bool readVar(bool &x);
bool readVar(short int &x);
bool readVar(int &x);
bool readVar(long int &x);
bool readVar(long long int &x);
bool readVar(unsigned short int &x);
bool readVar(unsigned int &x);
bool readVar(unsigned long &x);
bool readVar(unsigned long long &x);
bool readVar(std::string &x);
bool readVar(char &x);
bool readVar(char *&x);
bool readVar(float &x);
bool readVar(double &x);
bool readVar(long double &x);
template <typename T>
void writeInt(T x);
void writeString(std::string x);
void writeChar(char x);
void writeCharArray(char *x);
void writeFloat(float x);
template <typename T>
void writeDouble(T x);
void writeVar(bool x);
void writeVar(short int x);
void writeVar(int x);
void writeVar(long int x);
void writeVar(long long int x);
void writeVar(unsigned short int x);
void writeVar(unsigned int x);
void writeVar(unsigned long x);
void writeVar(unsigned long long x);
void writeVar(char x);
void writeVar(char *x);
void writeVar(std::string x);
void writeVar(float x);
void writeVar(double x);
void writeVar(long double x);
using namespace std;
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << '\n'; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
class segtree {
 public:
  struct node {
    long long mn = 0;
    long long add = 0;
    void apply(int l, int r, long long v) {
      mn += v;
      add += v;
    }
  };
  node unite(const node &a, const node &b) const {
    node res;
    res.mn = min(a.mn, b.mn);
    return res;
  }
  inline void push(int x, int l, int r) {
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    if (tree[x].add != 0) {
      tree[x + 1].apply(l, y, tree[x].add);
      tree[z].apply(y + 1, r, tree[x].add);
      tree[x].add = 0;
    }
  }
  inline void pull(int x, int z) { tree[x] = unite(tree[x + 1], tree[z]); }
  int n;
  vector<node> tree;
  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }
  template <typename M>
  void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tree[x].apply(l, r, v[l]);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }
  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }
  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M &...v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }
  int find_first_knowingly(int x, int l, int r,
                           const function<bool(const node &)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }
  int find_first(int x, int l, int r, int ll, int rr,
                 const function<bool(const node &)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  int find_last_knowingly(int x, int l, int r,
                          const function<bool(const node &)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }
  int find_last(int x, int l, int r, int ll, int rr,
                const function<bool(const node &)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }
  template <typename M>
  segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v);
  }
  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }
  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }
  template <typename... M>
  void modify(int ll, int rr, const M &...v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }
  int find_first(int ll, int rr, const function<bool(const node &)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }
  int find_last(int ll, int rr, const function<bool(const node &)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};
int main() {
  0;
  0;
  int n, tt;
  readVar(n), readVar(tt);
  vector<int> p(n);
  vector<int> w(n);
  for (int i = 1; i < n; i++) {
    readVar(p[i]), readVar(w[i]);
    p[i]--;
  }
  vector<vector<int>> qs(n);
  vector<int> L(tt), R(tt), v(tt);
  vector<long long> res(tt, -1);
  for (int i = 0; i < tt; i++) {
    readVar(v[i]), readVar(L[i]), readVar(R[i]);
    v[i]--;
    L[i]--;
    R[i]--;
    qs[v[i]].push_back(i);
  }
  vector<long long> dst(n);
  for (int i = 1; i < n; i++) {
    dst[i] = dst[p[i]] + w[i];
  }
  vector<int> is_leaf(n, 1);
  for (int i = 1; i < n; i++) {
    is_leaf[p[i]] = 0;
  }
  const long long inf = (long long)1e18;
  for (int i = 0; i < n; i++) {
    if (!is_leaf[i]) {
      dst[i] = inf;
    }
  }
  segtree st(dst);
  vector<int> stk;
  vector<int> to(n, n - 1);
  for (int i = 0; i < n; i++) {
    while (!stk.empty() && stk.back() != p[i]) {
      int u = stk.back();
      to[u] = i - 1;
      stk.pop_back();
    }
    stk.push_back(i);
  }
  42;
  stk.clear();
  for (int i = 0; i < n; i++) {
    while (!stk.empty() && stk.back() != p[i]) {
      int u = stk.back();
      st.modify(0, n - 1, -w[u]);
      st.modify(u, to[u], 2 * w[u]);
      stk.pop_back();
    }
    stk.push_back(i);
    st.modify(0, n - 1, w[i]);
    st.modify(i, to[i], -2 * w[i]);
    for (int id : qs[i]) {
      res[id] = st.get(L[id], R[id]).mn;
    }
  }
  for (int i = 0; i < tt; i++) {
    writeVar(res[i]), writeVar('\n');
  }
  return 0;
}
template <typename T>
bool readInt(T &x) {
  x = 0;
  T sig = 1;
  if (!remaining)
    readCharacter = getchar(), remaining = true;
  else
    remaining = false;
  while (!isdigit(readCharacter) && readCharacter != EOF)
    sig = (readCharacter == '-' ? -sig : sig), readCharacter = getchar();
  if (readCharacter == EOF) return remaining = false, false;
  while (isdigit(readCharacter) && readCharacter != EOF)
    x = x * 10 + readCharacter - '0', readCharacter = getchar();
  x *= sig;
  return true;
}
template <typename T>
bool readString(T &x) {
  x = "";
  if (!remaining)
    readCharacter = getchar(), remaining = true;
  else
    remaining = false;
  while (
      (readCharacter == '\n' || readCharacter == '\t' || readCharacter == ' '))
    readCharacter = getchar();
  if (readCharacter == EOF) return remaining = false, false;
  while ((readCharacter != '\n' && readCharacter != '\t' &&
          readCharacter != ' ' && readCharacter != EOF))
    x += readCharacter, readCharacter = getchar();
  return true;
}
template <typename T>
bool readChar(T &x) {
  if (!remaining)
    readCharacter = getchar();
  else
    remaining = false;
  if (readCharacter == EOF) return remaining = false, false;
  while (
      (readCharacter == '\n' || readCharacter == '\t' || readCharacter == ' '))
    readCharacter = getchar();
  remaining = false;
  x = readCharacter;
  return true;
}
bool readCharArray(char *&x) {
  std::string y;
  if (readString(y) == false) return false;
  x = new char[(int)y.size() + 1];
  strcpy(x, y.c_str());
  return true;
}
template <typename T>
bool readFloat(T &x) {
  return (scanf("%f", &x) != EOF);
}
template <typename T>
bool readDouble(T &x) {
  double y;
  if (scanf("%lf", &y) == EOF) return false;
  x = y;
  return true;
}
bool readVar(bool &x) {
  int aux;
  bool ret = readInt(aux);
  x = (aux != 0);
  return ret;
}
bool readVar(short int &x) { return readInt(x); }
bool readVar(int &x) { return readInt(x); }
bool readVar(long int &x) { return readInt(x); }
bool readVar(long long int &x) { return readInt(x); }
bool readVar(unsigned short int &x) { return readInt(x); }
bool readVar(unsigned int &x) { return readInt(x); }
bool readVar(unsigned long &x) { return readInt(x); }
bool readVar(unsigned long long &x) { return readInt(x); }
bool readVar(std::string &x) { return readString(x); }
bool readVar(char &x) { return readChar(x); }
bool readVar(char *&x) { return readCharArray(x); }
bool readVar(float &x) { return readFloat(x); }
bool readVar(double &x) { return readDouble(x); }
bool readVar(long double &x) { return readDouble(x); }
template <typename T>
void writeInt(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  char writeBuffer[20], *writePtr = writeBuffer;
  do {
    *writePtr++ = '0' + x % 10;
    x /= 10;
  } while (x);
  do {
    putchar(*--writePtr);
  } while (writePtr > writeBuffer);
}
void writeChar(char x) { putchar(x); }
void writeCharArray(char *x) {
  while (*x != '\0') putchar(*x++);
}
void writeString(std::string x) {
  for (char c : x) putchar(c);
}
void writeFloat(float x) { printf("%f", x); }
template <typename T>
void writeDouble(T x) {
  printf("%lf", (double)x);
}
void writeVar(bool x) { writeInt(x); }
void writeVar(short int x) { writeInt(x); }
void writeVar(int x) { writeInt(x); }
void writeVar(long int x) { writeInt(x); }
void writeVar(long long int x) { writeInt(x); }
void writeVar(unsigned short int x) { writeInt(x); }
void writeVar(unsigned int x) { writeInt(x); }
void writeVar(unsigned long x) { writeInt(x); }
void writeVar(unsigned long long x) { writeInt(x); }
void writeVar(std::string x) { writeString(x); }
void writeVar(char x) { writeChar(x); }
void writeVar(char *x) { writeCharArray(x); }
void writeVar(float x) { writeFloat(x); }
void writeVar(double x) { writeDouble(x); }
void writeVar(long double x) { writeDouble(x); }
