#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct edge {
  int x, y, l, Num;
  void fill(int _x, int _y, int _l) { x = _x, y = _y, l = _l; }
  bool friend operator<(const edge A, const edge B) { return A.l > B.l; }
} E[N], q[N];
int v[N], Res[N];
int n, Q;
struct segment {
  int l, r, mid, len, full;
  segment() { l = r = mid = len = full = 0; }
} Empty;
segment combine(segment A, segment B) {
  segment Res;
  if (A.full < 0) return B;
  if (B.full < 0) return A;
  if (A.full && B.full)
    Res.full = 1;
  else if (A.full)
    Res = B, Res.l += A.len;
  else if (B.full)
    Res = A, Res.r += B.len;
  else {
    Res.mid = v[A.r + B.l] + A.mid + B.mid;
    Res.l = A.l, Res.r = B.r;
  }
  Res.len = A.len + B.len;
  return Res;
}
namespace segT {
segment f[N << 2];
segment query(int x, int l, int r, int _l, int _r) {
  if (_l <= l && r <= _r) return f[x];
  if (r <= _l || _r <= l) return Empty;
  int mid = (l + r) >> 1;
  return combine(query(x << 1, l, mid, _l, _r),
                 query(x + x + 1, mid, r, _l, _r));
}
void modify(int x, int l, int r, int p) {
  if (l == r - 1) {
    f[x].full = f[x].len = 1;
    return;
  }
  int mid = (l + r) >> 1;
  if (p < mid)
    modify(x << 1, l, mid, p);
  else
    modify(x + x + 1, mid, r, p);
  f[x] = combine(f[x << 1], f[x + x + 1]);
}
}  // namespace segT
namespace lsd {
vector<int> e[N];
int que[N], dep[N], pos[N], grphd[N], fa[N], size[N], prf[N];
void preprocessing() {
  fill(fa, fa + N, -1);
  fill(pos, pos + N, -1);
  fill(prf, prf + N, -1);
  int x, hd, tl, Ti = 0;
  for (hd = 0, tl = 1, x = 0; hd < tl; x = que[++hd])
    for (int j = 0; j < e[x].size(); ++j)
      if (e[x][j] != fa[x])
        fa[que[tl++] = e[x][j]] = x, dep[e[x][j]] = dep[x] + 1;
  for (int i = n - 1; i >= 0; --i)
    if (++size[x = que[i]])
      for (int j = 0; j < e[x].size(); ++j) {
        if (e[x][j] == fa[x]) continue;
        size[x] += size[e[x][j]];
        if (prf[x] < 0 || size[e[x][j]] > size[prf[x]]) prf[x] = e[x][j];
      }
  for (int i = 0; i < n; ++i)
    if (pos[que[i]] < 0)
      for (int x = que[i]; x >= 0; x = prf[x]) pos[x] = Ti++, grphd[x] = que[i];
}
int query(int x, int y) {
  segment R1 = Empty, R2 = Empty, Temp;
  while (grphd[x] != grphd[y])
    if (dep[grphd[x]] > dep[grphd[y]]) {
      Temp = segT ::query(1, 0, n, pos[grphd[x]], pos[x] + 1);
      R1 = combine(Temp, R1), x = fa[grphd[x]];
    } else {
      Temp = segT ::query(1, 0, n, pos[grphd[y]], pos[y] + 1);
      R2 = combine(Temp, R2), y = fa[grphd[y]];
    }
  if (dep[x] > dep[y]) {
    Temp = segT ::query(1, 0, n, pos[y] + 1, pos[x] + 1);
    R1 = combine(Temp, R1);
  } else {
    Temp = segT ::query(1, 0, n, pos[x] + 1, pos[y] + 1);
    R2 = combine(Temp, R2);
  }
  swap(R1.l, R1.r);
  Temp = combine(R1, R2);
  if (Temp.full)
    return v[Temp.len];
  else
    return Temp.mid + v[Temp.l] + v[Temp.r];
}
}  // namespace lsd
void preprocessing() {
  int x, y, l;
  cin >> n >> Q;
  for (int i = 1; i < n; ++i) cin >> v[i];
  for (int i = 1; i < n; ++i) {
    cin >> x >> y >> l;
    E[i - 1].fill(--x, --y, l);
    lsd ::e[x].push_back(y), lsd ::e[y].push_back(x);
  }
  for (int i = 0; i < Q; ++i) {
    cin >> x >> y >> l;
    q[i].fill(x - 1, y - 1, l), q[i].Num = i;
  }
  sort(E, E + n - 1), sort(q, q + Q);
  lsd ::preprocessing(), Empty.full = -1;
  for (int i = 0; i < n - 1; ++i)
    if (lsd ::fa[E[i].x] == E[i].y) swap(E[i].x, E[i].y);
}
void solve() {
  int p = 0;
  for (int i = 0; i < Q; ++i) {
    while (p < n - 1 && E[p].l >= q[i].l)
      segT ::modify(1, 0, n, lsd ::pos[E[p++].y]);
    Res[q[i].Num] = lsd ::query(q[i].x, q[i].y);
  }
  for (int i = 0; i < Q; ++i) cout << Res[i] << endl;
}
int main() {
  ios ::sync_with_stdio(0);
  preprocessing();
  solve();
  return 0;
}

### Prompt

Your challenge is to write 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;
const int N = 100005;
struct edge {
  int x, y, l, Num;
  void fill(int _x, int _y, int _l) { x = _x, y = _y, l = _l; }
  bool friend operator<(const edge A, const edge B) { return A.l > B.l; }
} E[N], q[N];
int v[N], Res[N];
int n, Q;
struct segment {
  int l, r, mid, len, full;
  segment() { l = r = mid = len = full = 0; }
} Empty;
segment combine(segment A, segment B) {
  segment Res;
  if (A.full < 0) return B;
  if (B.full < 0) return A;
  if (A.full && B.full)
    Res.full = 1;
  else if (A.full)
    Res = B, Res.l += A.len;
  else if (B.full)
    Res = A, Res.r += B.len;
  else {
    Res.mid = v[A.r + B.l] + A.mid + B.mid;
    Res.l = A.l, Res.r = B.r;
  }
  Res.len = A.len + B.len;
  return Res;
}
namespace segT {
segment f[N << 2];
segment query(int x, int l, int r, int _l, int _r) {
  if (_l <= l && r <= _r) return f[x];
  if (r <= _l || _r <= l) return Empty;
  int mid = (l + r) >> 1;
  return combine(query(x << 1, l, mid, _l, _r),
                 query(x + x + 1, mid, r, _l, _r));
}
void modify(int x, int l, int r, int p) {
  if (l == r - 1) {
    f[x].full = f[x].len = 1;
    return;
  }
  int mid = (l + r) >> 1;
  if (p < mid)
    modify(x << 1, l, mid, p);
  else
    modify(x + x + 1, mid, r, p);
  f[x] = combine(f[x << 1], f[x + x + 1]);
}
}  // namespace segT
namespace lsd {
vector<int> e[N];
int que[N], dep[N], pos[N], grphd[N], fa[N], size[N], prf[N];
void preprocessing() {
  fill(fa, fa + N, -1);
  fill(pos, pos + N, -1);
  fill(prf, prf + N, -1);
  int x, hd, tl, Ti = 0;
  for (hd = 0, tl = 1, x = 0; hd < tl; x = que[++hd])
    for (int j = 0; j < e[x].size(); ++j)
      if (e[x][j] != fa[x])
        fa[que[tl++] = e[x][j]] = x, dep[e[x][j]] = dep[x] + 1;
  for (int i = n - 1; i >= 0; --i)
    if (++size[x = que[i]])
      for (int j = 0; j < e[x].size(); ++j) {
        if (e[x][j] == fa[x]) continue;
        size[x] += size[e[x][j]];
        if (prf[x] < 0 || size[e[x][j]] > size[prf[x]]) prf[x] = e[x][j];
      }
  for (int i = 0; i < n; ++i)
    if (pos[que[i]] < 0)
      for (int x = que[i]; x >= 0; x = prf[x]) pos[x] = Ti++, grphd[x] = que[i];
}
int query(int x, int y) {
  segment R1 = Empty, R2 = Empty, Temp;
  while (grphd[x] != grphd[y])
    if (dep[grphd[x]] > dep[grphd[y]]) {
      Temp = segT ::query(1, 0, n, pos[grphd[x]], pos[x] + 1);
      R1 = combine(Temp, R1), x = fa[grphd[x]];
    } else {
      Temp = segT ::query(1, 0, n, pos[grphd[y]], pos[y] + 1);
      R2 = combine(Temp, R2), y = fa[grphd[y]];
    }
  if (dep[x] > dep[y]) {
    Temp = segT ::query(1, 0, n, pos[y] + 1, pos[x] + 1);
    R1 = combine(Temp, R1);
  } else {
    Temp = segT ::query(1, 0, n, pos[x] + 1, pos[y] + 1);
    R2 = combine(Temp, R2);
  }
  swap(R1.l, R1.r);
  Temp = combine(R1, R2);
  if (Temp.full)
    return v[Temp.len];
  else
    return Temp.mid + v[Temp.l] + v[Temp.r];
}
}  // namespace lsd
void preprocessing() {
  int x, y, l;
  cin >> n >> Q;
  for (int i = 1; i < n; ++i) cin >> v[i];
  for (int i = 1; i < n; ++i) {
    cin >> x >> y >> l;
    E[i - 1].fill(--x, --y, l);
    lsd ::e[x].push_back(y), lsd ::e[y].push_back(x);
  }
  for (int i = 0; i < Q; ++i) {
    cin >> x >> y >> l;
    q[i].fill(x - 1, y - 1, l), q[i].Num = i;
  }
  sort(E, E + n - 1), sort(q, q + Q);
  lsd ::preprocessing(), Empty.full = -1;
  for (int i = 0; i < n - 1; ++i)
    if (lsd ::fa[E[i].x] == E[i].y) swap(E[i].x, E[i].y);
}
void solve() {
  int p = 0;
  for (int i = 0; i < Q; ++i) {
    while (p < n - 1 && E[p].l >= q[i].l)
      segT ::modify(1, 0, n, lsd ::pos[E[p++].y]);
    Res[q[i].Num] = lsd ::query(q[i].x, q[i].y);
  }
  for (int i = 0; i < Q; ++i) cout << Res[i] << endl;
}
int main() {
  ios ::sync_with_stdio(0);
  preprocessing();
  solve();
  return 0;
}

```