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>
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
using namespace std;
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
class Point {
 public:
  double x, y;
  Point(double x = 0, double y = 0) : x(x), y(y) {}
  Point operator+(Point p) { return Point(x + p.x, y + p.y); }
  Point operator-(Point p) { return Point(x - p.x, y - p.y); }
  Point operator*(double a) { return Point(x * a, y * a); }
  Point operator/(double a) { return Point(x / a, y / a); }
  double absv() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  bool operator<(const Point &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const Point &p) const {
    return fabs(x - p.x) < (1e-10) && fabs(y - p.y) < (1e-10);
  }
};
struct Segment {
  Point p1, p2;
};
double dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
bool parareru(Point a, Point b, Point c, Point d) {
  return abs(cross(a - b, d - c)) < (1e-10);
}
double distance_ls_p(Point a, Point b, Point c) {
  if (dot(b - a, c - a) < (1e-10)) return (c - a).absv();
  if (dot(a - b, c - b) < (1e-10)) return (c - b).absv();
  return abs(cross(b - a, c - a)) / (b - a).absv();
}
bool is_intersected_ls(Segment a, Segment b) {
  if (a.p1 == b.p1 || a.p2 == b.p1 || a.p1 == b.p2 || a.p2 == b.p2)
    return false;
  if (parareru((a.p2), (a.p1), (a.p1), (b.p2)) &&
      parareru((a.p2), (a.p1), (a.p1), (b.p1))) {
    if (dot(a.p1 - b.p1, a.p1 - b.p2) < (1e-10)) return true;
    if (dot(a.p2 - b.p1, a.p2 - b.p2) < (1e-10)) return true;
    if (dot(a.p1 - b.p1, a.p2 - b.p1) < (1e-10)) return true;
    if (dot(a.p1 - b.p2, a.p2 - b.p2) < (1e-10)) return true;
    return false;
  } else
    return (cross(a.p2 - a.p1, b.p1 - a.p1) * cross(a.p2 - a.p1, b.p2 - a.p1) <
            (1e-10)) &&
           (cross(b.p2 - b.p1, a.p1 - b.p1) * cross(b.p2 - b.p1, a.p2 - b.p1) <
            (1e-10));
}
double segment_dis(Segment a, Segment b) {
  if (is_intersected_ls(a, b)) return 0;
  double r = distance_ls_p(a.p1, a.p2, b.p1);
  r = min(r, distance_ls_p(a.p1, a.p2, b.p2));
  r = min(r, distance_ls_p(b.p1, b.p2, a.p2));
  r = min(r, distance_ls_p(b.p1, b.p2, a.p1));
  return r;
}
Point intersection_ls(Segment a, Segment b) {
  Point ba = b.p2 - b.p1;
  double d1 = abs(cross(ba, a.p1 - b.p1));
  double d2 = abs(cross(ba, a.p2 - b.p1));
  double t = d1 / (d1 + d2);
  return a.p1 + (a.p2 - a.p1) * t;
}
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long gcd(long long v, long long b) {
  if (v > b) return gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return gcd(v, b % v);
}
double distans(double x1, double y1, double x2, double y2) {
  double rr = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
  return sqrt(rr);
}
long long mod;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first + r.first, l.second + r.second};
}
long long pr[1200010];
long long inv[1200010];
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
double bekid(double w, long long r) {
  if (r == 0) return 1.0;
  if (r == 1) return w;
  if (r % 2) return bekid(w, r - 1) * w;
  double f = bekid(w, r / 2);
  return f * f;
}
long long comb(long long nn, long long rr) {
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i <= ert; i++) {
    pr[i] = (pr[i - 1] * i) % mod;
  }
  for (long long i = 0; i <= ert; i++) inv[i] = beki(pr[i], mod - 2, mod);
}
struct seg_rangeadd_getmin {
 private:
 public:
  long long cor = (1 << 19);
  long long inff = (long long)1000000007 * (long long)1000000007;
  vector<long long> vec;
  vector<long long> lazy;
  void shoki1() {
    vec.resize(2 * cor + 3, 0);
    lazy.resize(2 * cor + 3, 0);
  }
  void shoki2() {
    for (long long i = cor - 1; i > 0; i--) {
      vec[i] = min(vec[2 * i], vec[2 * i + 1]);
    }
  }
  void chien(long long k, long long l, long long r) {
    if (l + 1 < r) {
      vec[k] += lazy[k];
      lazy[2 * k] += lazy[k];
      lazy[2 * k + 1] += lazy[k];
      lazy[k] = 0;
    } else {
      vec[k] += lazy[k];
      lazy[k] = 0;
    }
  }
  long long rangeadd(long long a, long long b, long long w, long long k = 1,
                     long long l = 0, long long r = -3) {
    if (r < 0) r = cor;
    if (a <= l && r <= b) {
      lazy[k] += w;
      chien(k, l, r);
      return vec[k];
    }
    if (r <= a || b <= l) {
      chien(k, l, r);
      return vec[k];
    }
    chien(k, l, r);
    long long w1 = rangeadd(a, b, w, k * 2, l, (l + r) / 2);
    long long w2 = rangeadd(a, b, w, k * 2 + 1, (l + r) / 2, r);
    vec[k] = min(w1, w2);
    return vec[k];
  }
  long long getmin(long long a, long long b, long long k = 1, long long l = 0,
                   long long r = -1) {
    if (r < 0) r = cor;
    chien(k, l, r);
    if (r <= a || b <= l) {
      return inff;
    }
    if (a <= l && r <= b) {
      return vec[k];
    }
    long long w1 = getmin(a, b, k * 2, l, (l + r) / 2);
    long long w2 = getmin(a, b, k * 2 + 1, (l + r) / 2, r);
    return min(w1, w2);
  }
  void pre() {
    for (long long i = 1; i < 2 * cor; i++) {
      cout << vec[i] << " ";
      if (((i + 1) & (-(i + 1))) == i + 1) cout << endl;
    }
  }
};
seg_rangeadd_getmin ss;
vector<pair<long long, long long> > G[500020];
vector<long long> ve;
long long lef[500020], rig[500020];
long long dis[500020];
void f_dfs(long long r) {
  lef[r] = ve.size();
  if (G[r].size()) {
    for (auto v : G[r]) f_dfs(v.first);
  } else
    ve.push_back(r);
  rig[r] = ve.size();
}
void s_dfs(long long r, long long d = 0) {
  dis[r] = d;
  for (auto v : G[r]) {
    s_dfs(v.first, v.second + d);
  }
}
vector<pa3> que[500020];
long long ans[500020];
long long ha = 0;
long long zen = 0;
void dfs(long long r) {
  for (auto v : que[r]) {
    long long lq = lower_bound(ve.begin(), ve.end(), v.x) - ve.begin();
    long long rq = lower_bound(ve.begin(), ve.end(), v.y) - ve.begin();
    long long t = ss.getmin(lq, rq);
    ans[v.z] = t + zen;
  }
  for (auto v : G[r]) {
    zen += v.second;
    ss.rangeadd(lef[v.first], rig[v.first], -2 * v.second);
    dfs(v.first);
    zen -= v.second;
    ss.rangeadd(lef[v.first], rig[v.first], 2 * v.second);
  }
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n, q;
  cin >> n >> q;
  for (long long i = 2; i <= n; i++) {
    long long y, yy;
    cin >> y >> yy;
    G[y].push_back({i, yy});
  }
  for (long long i = 0; i < q; i++) {
    long long y, yy, yyy;
    cin >> yyy >> y >> yy;
    yy++;
    que[yyy].push_back({y, yy, i});
  }
  f_dfs(1);
  s_dfs(1);
  ss.shoki1();
  long long cnt = 0;
  for (long long i = 1; i <= n; i++) {
    if (G[i].size()) {
    } else {
      ss.vec[ss.cor + cnt] = dis[i], ha++;
      cnt++;
    }
  }
  ss.shoki2();
  dfs(1);
  for (long long i = 0; i < q; i++) cout << ans[i] << "\n";
  return 0;
}
