#include <bits/stdc++.h>
using namespace std;
const int MAX = 200100, TOUR = 1 << 18;
;
struct tour {
  int val, sz, poc, kraj;
} t[2 * TOUR];
int polje[MAX];
int subtree[MAX], hlroot[MAX], poz[MAX], par[MAX], wpar[MAX], dub[MAX];
int vr = 0;
pair<int, int> edge[MAX];
pair<int, int> q[MAX];
int qa[MAX], qb[MAX], rje[MAX];
vector<pair<int, int> > V[MAX];
tour Merge(tour a, tour b) {
  tour ret = {a.val + b.val, a.sz + b.sz, a.poc, b.kraj};
  if (a.poc == a.sz) ret.poc += b.poc;
  if (b.kraj == b.sz) ret.kraj += a.kraj;
  if (a.poc < a.sz && b.kraj < b.sz) ret.val += polje[a.kraj + b.poc];
  return ret;
}
void InitTour() {
  for (int i = 2 * TOUR - 1; i; i--) {
    if (i >= TOUR)
      t[i] = {0, 1, 0, 0};
    else
      t[i] = Merge(t[2 * i], t[2 * i + 1]);
  }
}
void Stavi(int pos) {
  t[pos + TOUR] = {0, 1, 1, 1};
  for (pos = (pos + TOUR) / 2; pos; pos /= 2)
    t[pos] = Merge(t[2 * pos], t[2 * pos + 1]);
}
tour Vrati(int pos, int lo, int hi, int begin, int end) {
  if (lo >= end || hi <= begin) return {0, 0, 0, 0};
  if (lo >= begin && hi <= end) return t[pos];
  return Merge(Vrati(2 * pos + 0, lo, (lo + hi) / 2, begin, end),
               Vrati(2 * pos + 1, (lo + hi) / 2, hi, begin, end));
}
int Rek1(int node, int prosli) {
  int ret = 1;
  for (int i = 0; i < (int)V[node].size(); i++)
    if (V[node][i].first != prosli) ret += Rek1(V[node][i].first, node);
  return subtree[node] = ret;
}
void Rek2(int node, int prosli, int kor) {
  if (kor == -1) kor = node;
  if (prosli != -1) dub[node] = dub[prosli] + 1;
  par[node] = prosli;
  poz[node] = vr++;
  hlroot[node] = kor;
  int maxx = -1, ind = -1;
  for (int i = 0; i < (int)V[node].size(); i++) {
    int nn = V[node][i].first;
    if (nn != prosli && subtree[nn] > maxx) {
      maxx = subtree[nn];
      ind = nn;
    }
    if (nn == prosli) wpar[node] = V[node][i].second;
  }
  if (ind != -1) Rek2(ind, node, kor);
  for (int i = 0; i < (int)V[node].size(); i++) {
    int nn = V[node][i].first;
    if (nn != ind && nn != prosli) Rek2(nn, node, -1);
  }
}
void HLD() {
  Rek1(0, -1);
  Rek2(0, -1, -1);
}
int Lca(int a, int b, int gran) {
  tour ta = {0, 0, 0, 0}, tb = {0, 0, 0, 0};
  for (;;) {
    if (hlroot[a] == hlroot[b]) {
      if (dub[a] > dub[b]) {
        swap(a, b);
        swap(ta, tb);
      }
      tb = Merge(Vrati(1, 0, TOUR, poz[a] + 1, poz[b] + 1), tb);
      swap(ta.poc, ta.kraj);
      ta = Merge(ta, tb);
      break;
    }
    if (dub[hlroot[a]] > dub[hlroot[b]]) {
      swap(a, b);
      swap(ta, tb);
    }
    tb = Merge(Vrati(1, 0, TOUR, poz[hlroot[b]] + 1, poz[b] + 1), tb);
    if (wpar[hlroot[b]] >= gran)
      tb = Merge({0, 1, 1, 1}, tb);
    else
      tb = Merge({0, 1, 0, 0}, tb);
    b = par[hlroot[b]];
  }
  int ret = ta.val;
  ret += polje[ta.poc];
  if (ta.poc != ta.sz) ret += polje[ta.kraj];
  return ret;
}
int main() {
  int n, brq;
  scanf("%d%d", &n, &brq);
  for (int i = 1; i < n; i++) scanf("%d", &polje[i]);
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    V[a].push_back(pair<int, int>(b, c));
    V[b].push_back(pair<int, int>(a, c));
  }
  HLD();
  for (int i = 0; i < brq; i++) {
    int l;
    scanf("%d%d%d", &qa[i], &qb[i], &l);
    qa[i]--;
    qb[i]--;
    q[i] = pair<int, int>(l, i);
  }
  for (int i = 1; i < n; i++) edge[i - 1] = pair<int, int>(wpar[i], i);
  sort(q, q + brq, greater<pair<int, int> >());
  sort(edge, edge + n - 1, greater<pair<int, int> >());
  InitTour();
  for (int i = 0, j = 0; i < brq; i++) {
    for (; j < n - 1 && edge[j].first >= q[i].first; j++)
      Stavi(poz[edge[j].second]);
    rje[q[i].second] = Lca(qa[q[i].second], qb[q[i].second], q[i].first);
  }
  for (int i = 0; i < brq; i++) printf("%d\n", rje[i]);
  return 0;
}

### Prompt

Please create a solution in cpp 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;
const int MAX = 200100, TOUR = 1 << 18;
;
struct tour {
  int val, sz, poc, kraj;
} t[2 * TOUR];
int polje[MAX];
int subtree[MAX], hlroot[MAX], poz[MAX], par[MAX], wpar[MAX], dub[MAX];
int vr = 0;
pair<int, int> edge[MAX];
pair<int, int> q[MAX];
int qa[MAX], qb[MAX], rje[MAX];
vector<pair<int, int> > V[MAX];
tour Merge(tour a, tour b) {
  tour ret = {a.val + b.val, a.sz + b.sz, a.poc, b.kraj};
  if (a.poc == a.sz) ret.poc += b.poc;
  if (b.kraj == b.sz) ret.kraj += a.kraj;
  if (a.poc < a.sz && b.kraj < b.sz) ret.val += polje[a.kraj + b.poc];
  return ret;
}
void InitTour() {
  for (int i = 2 * TOUR - 1; i; i--) {
    if (i >= TOUR)
      t[i] = {0, 1, 0, 0};
    else
      t[i] = Merge(t[2 * i], t[2 * i + 1]);
  }
}
void Stavi(int pos) {
  t[pos + TOUR] = {0, 1, 1, 1};
  for (pos = (pos + TOUR) / 2; pos; pos /= 2)
    t[pos] = Merge(t[2 * pos], t[2 * pos + 1]);
}
tour Vrati(int pos, int lo, int hi, int begin, int end) {
  if (lo >= end || hi <= begin) return {0, 0, 0, 0};
  if (lo >= begin && hi <= end) return t[pos];
  return Merge(Vrati(2 * pos + 0, lo, (lo + hi) / 2, begin, end),
               Vrati(2 * pos + 1, (lo + hi) / 2, hi, begin, end));
}
int Rek1(int node, int prosli) {
  int ret = 1;
  for (int i = 0; i < (int)V[node].size(); i++)
    if (V[node][i].first != prosli) ret += Rek1(V[node][i].first, node);
  return subtree[node] = ret;
}
void Rek2(int node, int prosli, int kor) {
  if (kor == -1) kor = node;
  if (prosli != -1) dub[node] = dub[prosli] + 1;
  par[node] = prosli;
  poz[node] = vr++;
  hlroot[node] = kor;
  int maxx = -1, ind = -1;
  for (int i = 0; i < (int)V[node].size(); i++) {
    int nn = V[node][i].first;
    if (nn != prosli && subtree[nn] > maxx) {
      maxx = subtree[nn];
      ind = nn;
    }
    if (nn == prosli) wpar[node] = V[node][i].second;
  }
  if (ind != -1) Rek2(ind, node, kor);
  for (int i = 0; i < (int)V[node].size(); i++) {
    int nn = V[node][i].first;
    if (nn != ind && nn != prosli) Rek2(nn, node, -1);
  }
}
void HLD() {
  Rek1(0, -1);
  Rek2(0, -1, -1);
}
int Lca(int a, int b, int gran) {
  tour ta = {0, 0, 0, 0}, tb = {0, 0, 0, 0};
  for (;;) {
    if (hlroot[a] == hlroot[b]) {
      if (dub[a] > dub[b]) {
        swap(a, b);
        swap(ta, tb);
      }
      tb = Merge(Vrati(1, 0, TOUR, poz[a] + 1, poz[b] + 1), tb);
      swap(ta.poc, ta.kraj);
      ta = Merge(ta, tb);
      break;
    }
    if (dub[hlroot[a]] > dub[hlroot[b]]) {
      swap(a, b);
      swap(ta, tb);
    }
    tb = Merge(Vrati(1, 0, TOUR, poz[hlroot[b]] + 1, poz[b] + 1), tb);
    if (wpar[hlroot[b]] >= gran)
      tb = Merge({0, 1, 1, 1}, tb);
    else
      tb = Merge({0, 1, 0, 0}, tb);
    b = par[hlroot[b]];
  }
  int ret = ta.val;
  ret += polje[ta.poc];
  if (ta.poc != ta.sz) ret += polje[ta.kraj];
  return ret;
}
int main() {
  int n, brq;
  scanf("%d%d", &n, &brq);
  for (int i = 1; i < n; i++) scanf("%d", &polje[i]);
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    V[a].push_back(pair<int, int>(b, c));
    V[b].push_back(pair<int, int>(a, c));
  }
  HLD();
  for (int i = 0; i < brq; i++) {
    int l;
    scanf("%d%d%d", &qa[i], &qb[i], &l);
    qa[i]--;
    qb[i]--;
    q[i] = pair<int, int>(l, i);
  }
  for (int i = 1; i < n; i++) edge[i - 1] = pair<int, int>(wpar[i], i);
  sort(q, q + brq, greater<pair<int, int> >());
  sort(edge, edge + n - 1, greater<pair<int, int> >());
  InitTour();
  for (int i = 0, j = 0; i < brq; i++) {
    for (; j < n - 1 && edge[j].first >= q[i].first; j++)
      Stavi(poz[edge[j].second]);
    rje[q[i].second] = Lca(qa[q[i].second], qb[q[i].second], q[i].first);
  }
  for (int i = 0; i < brq; i++) printf("%d\n", rje[i]);
  return 0;
}

```