#include <bits/stdc++.h>
using namespace std;
int n;
int q;
long long int f[100012];
struct st {
  int u;
  int v;
  int len;
  int index;
  st(int a, int b, int c, int index_ = -1) {
    u = a;
    v = b;
    len = c;
    index = index_;
  }
};
bool cmp(st a, st b) { return a.len < b.len; }
vector<int> vv[100012];
bool use[100012];
vector<int> v[100012];
int dep[100012];
int lcc[19][100012];
int sub_tree[100012];
inline void dfs(int b, int h = 0, int pre = -1) {
  use[b] = true;
  dep[b] = h;
  lcc[0][b] = pre;
  for (int i = 0; i < vv[b].size(); i++) {
    if (use[vv[b][i]]) {
      continue;
    }
    dfs(vv[b][i], h + 1, b);
    v[b].push_back(vv[b][i]);
    sub_tree[b] += sub_tree[vv[b][i]];
  }
  sub_tree[b]++;
}
void init() {
  for (int i = 0; i + 1 < 19; i++) {
    for (int j = 0; j < n; j++) {
      if (lcc[i][j] == -1) {
        lcc[i + 1][j] = -1;
        continue;
      }
      lcc[i + 1][j] = lcc[i][lcc[i][j]];
    }
  }
}
int lca(int a, int b) {
  if (dep[a] < dep[b]) {
    swap(a, b);
  }
  for (int i = 0; i < 19; i++) {
    if (((dep[a] - dep[b]) >> i) & 1) {
      a = lcc[i][a];
    }
  }
  if (a == b) {
    return a;
  }
  for (int i = 19 - 1; i >= 0; i--) {
    if (lcc[i][a] != lcc[i][b]) {
      a = lcc[i][a];
      b = lcc[i][b];
    }
  }
  return lcc[0][a];
}
vector<st> ed;
vector<st> query;
long long int ans[100012];
struct ss {
  int rang;
  int lef;
  int rig;
  long long int sum;
  ss() { rang = lef = rig = sum = 0; }
};
ss merge(ss a, ss b) {
  if (a.rang == 0) {
    return b;
  }
  if (b.rang == 0) {
    return a;
  }
  ss r;
  r.rang = a.rang + b.rang;
  r.sum = a.sum + b.sum;
  if (a.rig != a.rang && b.lef != b.rang) {
    r.sum += f[a.rig + b.lef];
  }
  if (a.lef < a.rang) {
    r.lef = a.lef;
  } else {
    r.lef = a.lef + b.lef;
  }
  if (b.rig < b.rang) {
    r.rig = b.rig;
  } else {
    r.rig = b.rig + a.rig;
  }
  return r;
}
long long int sum_up(ss a) {
  long long int r = a.sum;
  if (a.lef == a.rang) {
    r += f[a.lef];
  } else {
    r += f[a.lef] + f[a.rig];
  }
  return r;
}
class Segment_tree {
 public:
  vector<ss> seg;
  int N;

 private:
  inline void init(int b, int l, int r) {
    seg[b].rang = r - l;
    if (l + 1 == r) {
      return;
    }
    init(b * 2 + 1, l, (l + r) >> 1);
    init(b * 2 + 2, (l + r) >> 1, r);
  }

 public:
  void resize(int n) {
    N = n;
    seg.assign((n + 3) * 4 + 3, ss());
    init(0, 0, n);
  }

 private:
  inline void add2(int b, int l, int r, int ll) {
    if (l <= ll && ll < r) {
      if (l + 1 == r) {
        seg[b].rang = 1;
        seg[b].lef = 1;
        seg[b].rig = 1;
        return;
      }
      add2(b * 2 + 1, l, (l + r) >> 1, ll);
      add2(b * 2 + 2, (l + r) >> 1, r, ll);
      seg[b] = merge(seg[b * 2 + 1], seg[b * 2 + 2]);
    }
  }
  inline ss q2(int b, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return seg[b];
    }
    if (r <= ll || rr <= l) {
      return ss();
    }
    return merge(q2(b * 2 + 1, l, (l + r) >> 1, ll, rr),
                 q2(b * 2 + 2, (l + r) >> 1, r, ll, rr));
  }

 public:
  void add(int index) { add2(0, 0, N, index); }
  ss query(int l, int r) { return q2(0, 0, N, l, r + 1); }
};
int belong[100012];
int att[100012];
int pre_node[100012];
vector<Segment_tree> HL;
inline void dfs2(int b, int a, int c) {
  belong[b] = a;
  att[b] = c;
  if (v[b].size() == 0) {
    HL[a].resize(c + 1);
    return;
  }
  int ind = -1;
  int maxt = -1;
  for (int i = 0; i < v[b].size(); i++) {
    if (maxt < sub_tree[v[b][i]]) {
      maxt = sub_tree[v[b][i]];
      ind = i;
    }
  }
  for (int i = 0; i < v[b].size(); i++) {
    if (i == ind) {
      dfs2(v[b][i], a, c + 1);
    } else {
      HL.push_back(Segment_tree());
      pre_node[HL.size() - 1] = b;
      dfs2(v[b][i], HL.size() - 1, 0);
    }
  }
}
void adding(int deep) { HL[belong[deep]].add(att[deep]); }
int go(int a, int k) {
  for (int i = 0; i < 19; i++) {
    if ((k >> i) & 1) {
      a = lcc[i][a];
    }
  }
  return a;
}
ss go_up_lef(int a, int b) {
  if (dep[a] < dep[b]) {
    swap(a, b);
  }
  ss r;
  while (belong[a] != belong[b]) {
    r = merge(HL[belong[a]].query(0, att[a]), r);
    a = pre_node[belong[a]];
  }
  if (att[b] > att[a]) {
    exit(1);
  }
  r = merge(HL[belong[a]].query(att[b], att[a]), r);
  swap(r.lef, r.rig);
  return r;
}
ss go_up_rig(int a, int b) {
  if (dep[a] < dep[b]) {
    swap(a, b);
  }
  ss r;
  while (belong[a] != belong[b]) {
    r = merge(HL[belong[a]].query(0, att[a]), r);
    a = pre_node[belong[a]];
  }
  if (att[b] > att[a]) {
    exit(1);
  }
  r = merge(HL[belong[a]].query(att[b], att[a]), r);
  return r;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; i++) {
    scanf("%I64d", &f[i]);
  }
  for (int i = 1; i < n; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    vv[a].push_back(b);
    vv[b].push_back(a);
    int c;
    scanf("%d", &c);
    ed.push_back(st(a, b, c));
  }
  dfs(0);
  init();
  for (int i = 0; i < ed.size(); i++) {
    if (dep[ed[i].u] > dep[ed[i].v]) {
      swap(ed[i].u, ed[i].v);
    }
  }
  for (int i = 0; i < q; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    query.push_back(st(a, b, c, i));
  }
  sort(ed.begin(), ed.end(), cmp);
  sort(query.begin(), query.end(), cmp);
  reverse(ed.begin(), ed.end());
  reverse(query.begin(), query.end());
  int ed_index = 0;
  HL.push_back(Segment_tree());
  dfs2(0, 0, 0);
  pre_node[0] = -1;
  for (int i = 0; i < query.size(); i++) {
    int L = query[i].len;
    while (ed_index < ed.size() && ed[ed_index].len >= L) {
      adding(ed[ed_index].v);
      ed_index++;
    }
    int A = query[i].v;
    int B = query[i].u;
    int lc = lca(A, B);
    ss lef;
    ss rig;
    if (A != lc) {
      int to = go(A, dep[A] - dep[lc] - 1);
      lef = go_up_lef(to, A);
    } else {
      lef = ss();
    }
    if (B != lc) {
      int to = go(B, dep[B] - dep[lc] - 1);
      rig = go_up_rig(to, B);
    } else {
      rig = ss();
    }
    ans[query[i].index] = sum_up(merge(lef, rig));
  }
  for (int i = 0; i < q; i++) {
    printf("%I64d\n", ans[i]);
  }
  return 0;
}

### Prompt

Please formulate a cpp solution to the following problem:

Tavas lives in Tavaspolis. Tavaspolis has n cities numbered from 1 to n connected by n - 1 bidirectional roads. There exists a path between any two cities. Also each road has a length.

<image>

Tavas' favorite strings are binary strings (they contain only 0 and 1). For any binary string like s = s1s2... sk, T(s) is its Goodness. T(s) can be calculated as follows:

Consider there are exactly m blocks of 1s in this string (a block of 1s in s is a maximal consecutive substring of s that only contains 1) with lengths x1, x2, ..., xm.

Define <image> where f is a given sequence (if m = 0, then T(s) = 0).

Tavas loves queries. He asks you to answer q queries. In each query he gives you numbers v, u, l and you should print following number:

Consider the roads on the path from city v to city u: e1, e2, ..., ex.

Build the binary string b of length x such that: bi = 1 if and only if l ≤ w(ei) where w(e) is the length of road e.

You should print T(b) for this query.

Input

The first line of input contains integers n and q (2 ≤ n ≤ 105 and 1 ≤ q ≤ 105).

The next line contains n - 1 space separated integers f1, f2, ..., fn - 1 (|fi| ≤ 1000).

The next n - 1 lines contain the details of the roads. Each line contains integers v, u and w and it means that there's a road between cities v and u of length w (1 ≤ v, u ≤ n and 1 ≤ w ≤ 109).

The next q lines contain the details of the queries. Each line contains integers v, u, l (1 ≤ v, u ≤ n, v ≠ u and 1 ≤ l ≤ 109).

Output

Print the answer of each query in a single line.

Examples

Input

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


Output

10
10
0


Input

6 6
-5 0 0 2 10
1 2 1
2 3 2
3 4 5
4 5 1
5 6 5
1 6 1
1 6 2
1 6 5
3 6 5
4 6 4
1 4 2


Output

10
-5
-10
-10
-5
0

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
int q;
long long int f[100012];
struct st {
  int u;
  int v;
  int len;
  int index;
  st(int a, int b, int c, int index_ = -1) {
    u = a;
    v = b;
    len = c;
    index = index_;
  }
};
bool cmp(st a, st b) { return a.len < b.len; }
vector<int> vv[100012];
bool use[100012];
vector<int> v[100012];
int dep[100012];
int lcc[19][100012];
int sub_tree[100012];
inline void dfs(int b, int h = 0, int pre = -1) {
  use[b] = true;
  dep[b] = h;
  lcc[0][b] = pre;
  for (int i = 0; i < vv[b].size(); i++) {
    if (use[vv[b][i]]) {
      continue;
    }
    dfs(vv[b][i], h + 1, b);
    v[b].push_back(vv[b][i]);
    sub_tree[b] += sub_tree[vv[b][i]];
  }
  sub_tree[b]++;
}
void init() {
  for (int i = 0; i + 1 < 19; i++) {
    for (int j = 0; j < n; j++) {
      if (lcc[i][j] == -1) {
        lcc[i + 1][j] = -1;
        continue;
      }
      lcc[i + 1][j] = lcc[i][lcc[i][j]];
    }
  }
}
int lca(int a, int b) {
  if (dep[a] < dep[b]) {
    swap(a, b);
  }
  for (int i = 0; i < 19; i++) {
    if (((dep[a] - dep[b]) >> i) & 1) {
      a = lcc[i][a];
    }
  }
  if (a == b) {
    return a;
  }
  for (int i = 19 - 1; i >= 0; i--) {
    if (lcc[i][a] != lcc[i][b]) {
      a = lcc[i][a];
      b = lcc[i][b];
    }
  }
  return lcc[0][a];
}
vector<st> ed;
vector<st> query;
long long int ans[100012];
struct ss {
  int rang;
  int lef;
  int rig;
  long long int sum;
  ss() { rang = lef = rig = sum = 0; }
};
ss merge(ss a, ss b) {
  if (a.rang == 0) {
    return b;
  }
  if (b.rang == 0) {
    return a;
  }
  ss r;
  r.rang = a.rang + b.rang;
  r.sum = a.sum + b.sum;
  if (a.rig != a.rang && b.lef != b.rang) {
    r.sum += f[a.rig + b.lef];
  }
  if (a.lef < a.rang) {
    r.lef = a.lef;
  } else {
    r.lef = a.lef + b.lef;
  }
  if (b.rig < b.rang) {
    r.rig = b.rig;
  } else {
    r.rig = b.rig + a.rig;
  }
  return r;
}
long long int sum_up(ss a) {
  long long int r = a.sum;
  if (a.lef == a.rang) {
    r += f[a.lef];
  } else {
    r += f[a.lef] + f[a.rig];
  }
  return r;
}
class Segment_tree {
 public:
  vector<ss> seg;
  int N;

 private:
  inline void init(int b, int l, int r) {
    seg[b].rang = r - l;
    if (l + 1 == r) {
      return;
    }
    init(b * 2 + 1, l, (l + r) >> 1);
    init(b * 2 + 2, (l + r) >> 1, r);
  }

 public:
  void resize(int n) {
    N = n;
    seg.assign((n + 3) * 4 + 3, ss());
    init(0, 0, n);
  }

 private:
  inline void add2(int b, int l, int r, int ll) {
    if (l <= ll && ll < r) {
      if (l + 1 == r) {
        seg[b].rang = 1;
        seg[b].lef = 1;
        seg[b].rig = 1;
        return;
      }
      add2(b * 2 + 1, l, (l + r) >> 1, ll);
      add2(b * 2 + 2, (l + r) >> 1, r, ll);
      seg[b] = merge(seg[b * 2 + 1], seg[b * 2 + 2]);
    }
  }
  inline ss q2(int b, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return seg[b];
    }
    if (r <= ll || rr <= l) {
      return ss();
    }
    return merge(q2(b * 2 + 1, l, (l + r) >> 1, ll, rr),
                 q2(b * 2 + 2, (l + r) >> 1, r, ll, rr));
  }

 public:
  void add(int index) { add2(0, 0, N, index); }
  ss query(int l, int r) { return q2(0, 0, N, l, r + 1); }
};
int belong[100012];
int att[100012];
int pre_node[100012];
vector<Segment_tree> HL;
inline void dfs2(int b, int a, int c) {
  belong[b] = a;
  att[b] = c;
  if (v[b].size() == 0) {
    HL[a].resize(c + 1);
    return;
  }
  int ind = -1;
  int maxt = -1;
  for (int i = 0; i < v[b].size(); i++) {
    if (maxt < sub_tree[v[b][i]]) {
      maxt = sub_tree[v[b][i]];
      ind = i;
    }
  }
  for (int i = 0; i < v[b].size(); i++) {
    if (i == ind) {
      dfs2(v[b][i], a, c + 1);
    } else {
      HL.push_back(Segment_tree());
      pre_node[HL.size() - 1] = b;
      dfs2(v[b][i], HL.size() - 1, 0);
    }
  }
}
void adding(int deep) { HL[belong[deep]].add(att[deep]); }
int go(int a, int k) {
  for (int i = 0; i < 19; i++) {
    if ((k >> i) & 1) {
      a = lcc[i][a];
    }
  }
  return a;
}
ss go_up_lef(int a, int b) {
  if (dep[a] < dep[b]) {
    swap(a, b);
  }
  ss r;
  while (belong[a] != belong[b]) {
    r = merge(HL[belong[a]].query(0, att[a]), r);
    a = pre_node[belong[a]];
  }
  if (att[b] > att[a]) {
    exit(1);
  }
  r = merge(HL[belong[a]].query(att[b], att[a]), r);
  swap(r.lef, r.rig);
  return r;
}
ss go_up_rig(int a, int b) {
  if (dep[a] < dep[b]) {
    swap(a, b);
  }
  ss r;
  while (belong[a] != belong[b]) {
    r = merge(HL[belong[a]].query(0, att[a]), r);
    a = pre_node[belong[a]];
  }
  if (att[b] > att[a]) {
    exit(1);
  }
  r = merge(HL[belong[a]].query(att[b], att[a]), r);
  return r;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; i++) {
    scanf("%I64d", &f[i]);
  }
  for (int i = 1; i < n; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    vv[a].push_back(b);
    vv[b].push_back(a);
    int c;
    scanf("%d", &c);
    ed.push_back(st(a, b, c));
  }
  dfs(0);
  init();
  for (int i = 0; i < ed.size(); i++) {
    if (dep[ed[i].u] > dep[ed[i].v]) {
      swap(ed[i].u, ed[i].v);
    }
  }
  for (int i = 0; i < q; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    query.push_back(st(a, b, c, i));
  }
  sort(ed.begin(), ed.end(), cmp);
  sort(query.begin(), query.end(), cmp);
  reverse(ed.begin(), ed.end());
  reverse(query.begin(), query.end());
  int ed_index = 0;
  HL.push_back(Segment_tree());
  dfs2(0, 0, 0);
  pre_node[0] = -1;
  for (int i = 0; i < query.size(); i++) {
    int L = query[i].len;
    while (ed_index < ed.size() && ed[ed_index].len >= L) {
      adding(ed[ed_index].v);
      ed_index++;
    }
    int A = query[i].v;
    int B = query[i].u;
    int lc = lca(A, B);
    ss lef;
    ss rig;
    if (A != lc) {
      int to = go(A, dep[A] - dep[lc] - 1);
      lef = go_up_lef(to, A);
    } else {
      lef = ss();
    }
    if (B != lc) {
      int to = go(B, dep[B] - dep[lc] - 1);
      rig = go_up_rig(to, B);
    } else {
      rig = ss();
    }
    ans[query[i].index] = sum_up(merge(lef, rig));
  }
  for (int i = 0; i < q; i++) {
    printf("%I64d\n", ans[i]);
  }
  return 0;
}

```