#include <bits/stdc++.h>
using namespace std;
int N, Q;
int first[100007];
int val[100007];
int team[100007];
int si[100007];
int anc[25][100007];
int level[100007];
vector<pair<int, int> > connections[100007];
vector<tuple<int, int, int, int> > queries;
vector<tuple<int, int, int, int>*> trees;
vector<int> stS;
vector<int> firstLevel;
vector<int> lastLevel;
vector<pair<int, int> > pairVals;
int sol[100007];
inline tuple<int, int, int, int> mergeTis(tuple<int, int, int, int> a,
                                          tuple<int, int, int, int> b) {
  int fir = get<0>(a);
  if (get<2>(a) == get<0>(a)) {
    fir += get<0>(b);
  }
  int las = get<1>(b);
  if (get<2>(b) == get<1>(b)) {
    las += get<1>(a);
  }
  int coun = get<2>(a) + get<2>(b);
  int su = get<3>(a) + get<3>(b) + first[get<1>(a) + get<0>(b)] -
           first[get<1>(a)] - first[get<0>(b)];
  return make_tuple(fir, las, coun, su);
}
tuple<int, int, int, int> quer(tuple<int, int, int, int>* st, int pos, int rs,
                               int re, int ns, int ne) {
  if (rs > ne || ns > re) {
    return make_tuple(0, 0, 0, 0);
  }
  if (ns <= rs && re <= ne) {
    return st[pos];
  }
  return mergeTis(quer(st, 2 * pos + 1, rs, (rs + re) / 2, ns, ne),
                  quer(st, 2 * pos + 2, (rs + re) / 2 + 1, re, ns, ne));
}
void add1(tuple<int, int, int, int>* st, int pos, int rs, int re, int posi) {
  if (posi < rs || posi > re) {
    return;
  }
  if (rs == re) {
    st[pos] = make_tuple(1, 1, 1, first[1]);
    return;
  }
  add1(st, 2 * pos + 1, rs, (rs + re) / 2, posi);
  add1(st, 2 * pos + 2, (rs + re) / 2 + 1, re, posi);
  st[pos] = mergeTis(st[2 * pos + 1], st[2 * pos + 2]);
}
void dfs(int pos, int par, int v, int lev) {
  val[pos] = v;
  pairVals.push_back(make_pair(pos, v));
  anc[0][pos] = par;
  for (int i = 1; i < 25; i++) {
    anc[i][pos] = anc[i - 1][anc[i - 1][pos]];
  }
  si[pos] = 1;
  level[pos] = lev;
  for (int i = 0; i < connections[pos].size(); i++) {
    int p = connections[pos][i].first, va = connections[pos][i].second;
    if (p != par) {
      dfs(p, pos, va, lev + 1);
      si[pos] += si[p];
    }
  }
}
void dfs2(int pos, int t) {
  if (t == -1) {
    t = trees.size();
    trees.push_back(NULL);
    stS.push_back(0);
    firstLevel.push_back(level[pos]);
    lastLevel.push_back(level[pos]);
  }
  team[pos] = t;
  lastLevel[t] = level[pos];
  int maxChild = -1;
  int maxNum = 0;
  for (int i = 0; i < connections[pos].size(); i++) {
    int p = connections[pos][i].first;
    if (p != anc[0][pos]) {
      if (si[p] > maxNum) {
        maxChild = p;
        maxNum = si[p];
      }
    }
  }
  for (int i = 0; i < connections[pos].size(); i++) {
    int p = connections[pos][i].first;
    if (p != anc[0][pos]) {
      if (p == maxChild) {
        dfs2(p, t);
      } else {
        dfs2(p, -1);
      }
    }
  }
}
inline int getAncestor(int a, int lev) {
  if (level[a] == lev) {
    return a;
  }
  int minPow = log2(level[a] - lev);
  return getAncestor(anc[minPow][a], lev);
}
inline int lca(int a, int b) {
  if (level[a] < level[b]) {
    swap(a, b);
  }
  a = getAncestor(a, level[b]);
  if (a == b) {
    return a;
  }
  for (int i = 24; i >= 0; i--) {
    if (anc[i][a] != anc[i][b]) {
      a = anc[i][a];
      b = anc[i][b];
    }
  }
  return anc[0][a];
}
inline bool comp1(pair<int, int> a, pair<int, int> b) {
  return a.second > b.second;
}
inline bool comp2(tuple<int, int, int, int> a, tuple<int, int, int, int> b) {
  return get<2>(a) > get<2>(b);
}
inline tuple<int, int, int, int> getVal(int a, int b) {
  if (a == b) {
    return make_tuple(0, 0, 0, 0);
  }
  int t = team[a];
  int maxLevel = max(level[b] + 1, firstLevel[t]);
  tuple<int, int, int, int> p =
      quer(trees[t], 0, 0, stS[t] / 2, maxLevel - firstLevel[t],
           level[a] - firstLevel[t]);
  tuple<int, int, int, int> p2 = getVal(getAncestor(a, maxLevel - 1), b);
  return mergeTis(p2, p);
}
int main() {
  scanf("%d %d", &N, &Q);
  for (int i = 1; i < N; i++) {
    scanf("%d", first + i);
  }
  for (int i = 0; i < N - 1; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    connections[u].push_back(make_pair(v, w));
    connections[v].push_back(make_pair(u, w));
  }
  dfs(1, 0, -1, 0);
  dfs2(1, -1);
  for (int i = 0; i < trees.size(); i++) {
    stS[i] = 2 * pow(2, ceil(log2(lastLevel[i] - firstLevel[i] + 1))) - 1;
    trees[i] = new tuple<int, int, int, int>[stS[i]];
    for (int j = stS[i] / 2; j < stS[i]; j++) {
      trees[i][j] = make_tuple(0, 0, 1, 0);
    }
    for (int j = stS[i] / 2 - 1; j >= 0; j--) {
      trees[i][j] = mergeTis(trees[i][2 * j + 1], trees[i][2 * j + 2]);
    }
  }
  sort(pairVals.begin(), pairVals.end(), comp1);
  for (int i = 0; i < Q; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    queries.push_back(make_tuple(a, b, c, i));
  }
  sort(queries.begin(), queries.end(), comp2);
  int curr = 0;
  for (int i = 0; i < queries.size(); i++) {
    auto q = queries[i];
    int a = get<0>(q), b = get<1>(q), l = get<2>(q);
    while (curr < N && l <= pairVals[curr].second) {
      int pos = pairVals[curr].first;
      int t = team[pos];
      int lev = level[pos];
      add1(trees[t], 0, 0, stS[t] / 2, lev - firstLevel[t]);
      curr++;
    }
    int lc = lca(a, b);
    tuple<int, int, int, int> v1 = getVal(a, lc);
    tuple<int, int, int, int> v2 = getVal(b, lc);
    swap(get<0>(v1), get<1>(v1));
    tuple<int, int, int, int> solu = mergeTis(v1, v2);
    sol[get<3>(q)] = get<3>(solu);
  }
  for (int i = 0; i < Q; i++) {
    printf("%d\n", sol[i]);
  }
  return 0;
}

### Prompt

Your task is to create 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, Q;
int first[100007];
int val[100007];
int team[100007];
int si[100007];
int anc[25][100007];
int level[100007];
vector<pair<int, int> > connections[100007];
vector<tuple<int, int, int, int> > queries;
vector<tuple<int, int, int, int>*> trees;
vector<int> stS;
vector<int> firstLevel;
vector<int> lastLevel;
vector<pair<int, int> > pairVals;
int sol[100007];
inline tuple<int, int, int, int> mergeTis(tuple<int, int, int, int> a,
                                          tuple<int, int, int, int> b) {
  int fir = get<0>(a);
  if (get<2>(a) == get<0>(a)) {
    fir += get<0>(b);
  }
  int las = get<1>(b);
  if (get<2>(b) == get<1>(b)) {
    las += get<1>(a);
  }
  int coun = get<2>(a) + get<2>(b);
  int su = get<3>(a) + get<3>(b) + first[get<1>(a) + get<0>(b)] -
           first[get<1>(a)] - first[get<0>(b)];
  return make_tuple(fir, las, coun, su);
}
tuple<int, int, int, int> quer(tuple<int, int, int, int>* st, int pos, int rs,
                               int re, int ns, int ne) {
  if (rs > ne || ns > re) {
    return make_tuple(0, 0, 0, 0);
  }
  if (ns <= rs && re <= ne) {
    return st[pos];
  }
  return mergeTis(quer(st, 2 * pos + 1, rs, (rs + re) / 2, ns, ne),
                  quer(st, 2 * pos + 2, (rs + re) / 2 + 1, re, ns, ne));
}
void add1(tuple<int, int, int, int>* st, int pos, int rs, int re, int posi) {
  if (posi < rs || posi > re) {
    return;
  }
  if (rs == re) {
    st[pos] = make_tuple(1, 1, 1, first[1]);
    return;
  }
  add1(st, 2 * pos + 1, rs, (rs + re) / 2, posi);
  add1(st, 2 * pos + 2, (rs + re) / 2 + 1, re, posi);
  st[pos] = mergeTis(st[2 * pos + 1], st[2 * pos + 2]);
}
void dfs(int pos, int par, int v, int lev) {
  val[pos] = v;
  pairVals.push_back(make_pair(pos, v));
  anc[0][pos] = par;
  for (int i = 1; i < 25; i++) {
    anc[i][pos] = anc[i - 1][anc[i - 1][pos]];
  }
  si[pos] = 1;
  level[pos] = lev;
  for (int i = 0; i < connections[pos].size(); i++) {
    int p = connections[pos][i].first, va = connections[pos][i].second;
    if (p != par) {
      dfs(p, pos, va, lev + 1);
      si[pos] += si[p];
    }
  }
}
void dfs2(int pos, int t) {
  if (t == -1) {
    t = trees.size();
    trees.push_back(NULL);
    stS.push_back(0);
    firstLevel.push_back(level[pos]);
    lastLevel.push_back(level[pos]);
  }
  team[pos] = t;
  lastLevel[t] = level[pos];
  int maxChild = -1;
  int maxNum = 0;
  for (int i = 0; i < connections[pos].size(); i++) {
    int p = connections[pos][i].first;
    if (p != anc[0][pos]) {
      if (si[p] > maxNum) {
        maxChild = p;
        maxNum = si[p];
      }
    }
  }
  for (int i = 0; i < connections[pos].size(); i++) {
    int p = connections[pos][i].first;
    if (p != anc[0][pos]) {
      if (p == maxChild) {
        dfs2(p, t);
      } else {
        dfs2(p, -1);
      }
    }
  }
}
inline int getAncestor(int a, int lev) {
  if (level[a] == lev) {
    return a;
  }
  int minPow = log2(level[a] - lev);
  return getAncestor(anc[minPow][a], lev);
}
inline int lca(int a, int b) {
  if (level[a] < level[b]) {
    swap(a, b);
  }
  a = getAncestor(a, level[b]);
  if (a == b) {
    return a;
  }
  for (int i = 24; i >= 0; i--) {
    if (anc[i][a] != anc[i][b]) {
      a = anc[i][a];
      b = anc[i][b];
    }
  }
  return anc[0][a];
}
inline bool comp1(pair<int, int> a, pair<int, int> b) {
  return a.second > b.second;
}
inline bool comp2(tuple<int, int, int, int> a, tuple<int, int, int, int> b) {
  return get<2>(a) > get<2>(b);
}
inline tuple<int, int, int, int> getVal(int a, int b) {
  if (a == b) {
    return make_tuple(0, 0, 0, 0);
  }
  int t = team[a];
  int maxLevel = max(level[b] + 1, firstLevel[t]);
  tuple<int, int, int, int> p =
      quer(trees[t], 0, 0, stS[t] / 2, maxLevel - firstLevel[t],
           level[a] - firstLevel[t]);
  tuple<int, int, int, int> p2 = getVal(getAncestor(a, maxLevel - 1), b);
  return mergeTis(p2, p);
}
int main() {
  scanf("%d %d", &N, &Q);
  for (int i = 1; i < N; i++) {
    scanf("%d", first + i);
  }
  for (int i = 0; i < N - 1; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    connections[u].push_back(make_pair(v, w));
    connections[v].push_back(make_pair(u, w));
  }
  dfs(1, 0, -1, 0);
  dfs2(1, -1);
  for (int i = 0; i < trees.size(); i++) {
    stS[i] = 2 * pow(2, ceil(log2(lastLevel[i] - firstLevel[i] + 1))) - 1;
    trees[i] = new tuple<int, int, int, int>[stS[i]];
    for (int j = stS[i] / 2; j < stS[i]; j++) {
      trees[i][j] = make_tuple(0, 0, 1, 0);
    }
    for (int j = stS[i] / 2 - 1; j >= 0; j--) {
      trees[i][j] = mergeTis(trees[i][2 * j + 1], trees[i][2 * j + 2]);
    }
  }
  sort(pairVals.begin(), pairVals.end(), comp1);
  for (int i = 0; i < Q; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    queries.push_back(make_tuple(a, b, c, i));
  }
  sort(queries.begin(), queries.end(), comp2);
  int curr = 0;
  for (int i = 0; i < queries.size(); i++) {
    auto q = queries[i];
    int a = get<0>(q), b = get<1>(q), l = get<2>(q);
    while (curr < N && l <= pairVals[curr].second) {
      int pos = pairVals[curr].first;
      int t = team[pos];
      int lev = level[pos];
      add1(trees[t], 0, 0, stS[t] / 2, lev - firstLevel[t]);
      curr++;
    }
    int lc = lca(a, b);
    tuple<int, int, int, int> v1 = getVal(a, lc);
    tuple<int, int, int, int> v2 = getVal(b, lc);
    swap(get<0>(v1), get<1>(v1));
    tuple<int, int, int, int> solu = mergeTis(v1, v2);
    sol[get<3>(q)] = get<3>(solu);
  }
  for (int i = 0; i < Q; i++) {
    printf("%d\n", sol[i]);
  }
  return 0;
}

```