#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int n, q;
int par[N], dep[N], siz[N], mxc[N], anc[N], dfn[N], dfo[N];
int Ut[N], Vt[N], Wt[N], ordt[N];
int Uq[N], Vq[N], Wq[N], ordq[N], res[N];
int F[N];
int lb[N], rb[N], lc[N], rc[N];
vector<int> B[N], C[N];
struct P {
  int l, r, v, f;
  P(int _l = 0, int _r = 0, int _v = 0, int _f = 0) {
    l = _l;
    r = _r;
    v = _v;
    f = _f;
  }
} val[N];
P rev(P a) { return P(a.r, a.l, a.v, a.f); }
P operator+(P a, P b) {
  if (!a.f && !b.f)
    return P(a.l, b.r, a.v + b.v + F[a.r + b.l], 0);
  else if (!a.f && b.f)
    return P(a.l, a.r + b.r, a.v, 0);
  else if (a.f && !b.f)
    return P(a.l + b.l, b.r, b.v, 0);
  else
    return P(a.l + b.l, a.r + b.r, 0, 1);
}
P d1() { return P(1, 1, 0, 1); }
void dfs1(int t = 1, int f = 0, int d = 0) {
  par[t] = f;
  dep[t] = d;
  siz[t] = 1;
  for (auto p : B[t])
    if (p != f) {
      dfs1(p, t, d + 1);
      siz[t] += siz[p];
      if (siz[p] > siz[mxc[t]]) mxc[t] = p;
    }
}
void dfs2(int t = 1, int p = 1) {
  static int tot = 0;
  dfo[++tot] = t;
  dfn[t] = tot;
  anc[t] = p;
  if (mxc[t]) dfs2(mxc[t], p);
  for (auto p : B[t])
    if (p != mxc[t] && p != par[t]) dfs2(p, p);
}
int build(int l, int r) {
  static int tot = 0;
  int t = ++tot;
  lb[t] = l;
  rb[t] = r;
  if (l < r) {
    lc[t] = build(l, (l + r) / 2);
    rc[t] = build((l + r) / 2 + 1, r);
    val[t] = val[lc[t]] + val[rc[t]];
  } else {
    if (dfo[l] <= n) val[t] = P(0, 0, 0, 1);
  }
  return t;
}
void modify(int t, int p) {
  if (lb[t] == rb[t])
    val[t] = P(1, 1, 0, 1);
  else {
    if (p <= rb[lc[t]])
      modify(lc[t], p);
    else
      modify(rc[t], p);
    val[t] = val[lc[t]] + val[rc[t]];
  }
}
P query(int t, int l, int r) {
  if (l <= lb[t] && rb[t] <= r) return val[t];
  if (r <= rb[lc[t]]) return query(lc[t], l, r);
  if (l >= lb[rc[t]]) return query(rc[t], l, r);
  return query(lc[t], l, r) + query(rc[t], l, r);
}
int query(int a, int b) {
  P A = P(0, 0, 0, 1), B = P(0, 0, 0, 1);
  while (1) {
    if (anc[a] != anc[b]) {
      if (dep[anc[a]] < dep[anc[b]]) swap(a, b), swap(A, B);
      A = query(1, dfn[anc[a]], dfn[a]) + A;
      a = par[anc[a]];
    } else {
      if (dep[a] > dep[b]) swap(a, b), swap(A, B);
      return (P() + rev(A) + query(1, dfn[a], dfn[b]) + B + P()).v;
    }
  }
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; ++i) scanf("%d", &F[i]);
  for (int i = 1; i < n; ++i) {
    scanf("%d%d%d", &Ut[i], &Vt[i], &Wt[i]);
    B[Ut[i]].push_back(i + n);
    B[i + n].push_back(Ut[i]);
    B[Vt[i]].push_back(i + n);
    B[i + n].push_back(Vt[i]);
  }
  for (int i = 1; i <= q; ++i) scanf("%d%d%d", &Uq[i], &Vq[i], &Wq[i]);
  for (int i = 1; i < n; ++i) ordt[i] = i;
  sort(ordt + 1, ordt + n, [](int a, int b) { return Wt[a] > Wt[b]; });
  for (int i = 1; i <= q; ++i) ordq[i] = i;
  sort(ordq + 1, ordq + q + 1, [](int a, int b) { return Wq[a] > Wq[b]; });
  dfs1();
  dfs2();
  build(1, n + n - 1);
  for (int i = 1, j = 1; i <= q; ++i) {
    while (j < n && Wt[ordt[j]] >= Wq[ordq[i]]) {
      modify(1, dfn[ordt[j] + n]);
      j++;
    }
    res[ordq[i]] = query(Uq[ordq[i]], Vq[ordq[i]]);
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", res[i]);
}

### 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 N = 1e6;
int n, q;
int par[N], dep[N], siz[N], mxc[N], anc[N], dfn[N], dfo[N];
int Ut[N], Vt[N], Wt[N], ordt[N];
int Uq[N], Vq[N], Wq[N], ordq[N], res[N];
int F[N];
int lb[N], rb[N], lc[N], rc[N];
vector<int> B[N], C[N];
struct P {
  int l, r, v, f;
  P(int _l = 0, int _r = 0, int _v = 0, int _f = 0) {
    l = _l;
    r = _r;
    v = _v;
    f = _f;
  }
} val[N];
P rev(P a) { return P(a.r, a.l, a.v, a.f); }
P operator+(P a, P b) {
  if (!a.f && !b.f)
    return P(a.l, b.r, a.v + b.v + F[a.r + b.l], 0);
  else if (!a.f && b.f)
    return P(a.l, a.r + b.r, a.v, 0);
  else if (a.f && !b.f)
    return P(a.l + b.l, b.r, b.v, 0);
  else
    return P(a.l + b.l, a.r + b.r, 0, 1);
}
P d1() { return P(1, 1, 0, 1); }
void dfs1(int t = 1, int f = 0, int d = 0) {
  par[t] = f;
  dep[t] = d;
  siz[t] = 1;
  for (auto p : B[t])
    if (p != f) {
      dfs1(p, t, d + 1);
      siz[t] += siz[p];
      if (siz[p] > siz[mxc[t]]) mxc[t] = p;
    }
}
void dfs2(int t = 1, int p = 1) {
  static int tot = 0;
  dfo[++tot] = t;
  dfn[t] = tot;
  anc[t] = p;
  if (mxc[t]) dfs2(mxc[t], p);
  for (auto p : B[t])
    if (p != mxc[t] && p != par[t]) dfs2(p, p);
}
int build(int l, int r) {
  static int tot = 0;
  int t = ++tot;
  lb[t] = l;
  rb[t] = r;
  if (l < r) {
    lc[t] = build(l, (l + r) / 2);
    rc[t] = build((l + r) / 2 + 1, r);
    val[t] = val[lc[t]] + val[rc[t]];
  } else {
    if (dfo[l] <= n) val[t] = P(0, 0, 0, 1);
  }
  return t;
}
void modify(int t, int p) {
  if (lb[t] == rb[t])
    val[t] = P(1, 1, 0, 1);
  else {
    if (p <= rb[lc[t]])
      modify(lc[t], p);
    else
      modify(rc[t], p);
    val[t] = val[lc[t]] + val[rc[t]];
  }
}
P query(int t, int l, int r) {
  if (l <= lb[t] && rb[t] <= r) return val[t];
  if (r <= rb[lc[t]]) return query(lc[t], l, r);
  if (l >= lb[rc[t]]) return query(rc[t], l, r);
  return query(lc[t], l, r) + query(rc[t], l, r);
}
int query(int a, int b) {
  P A = P(0, 0, 0, 1), B = P(0, 0, 0, 1);
  while (1) {
    if (anc[a] != anc[b]) {
      if (dep[anc[a]] < dep[anc[b]]) swap(a, b), swap(A, B);
      A = query(1, dfn[anc[a]], dfn[a]) + A;
      a = par[anc[a]];
    } else {
      if (dep[a] > dep[b]) swap(a, b), swap(A, B);
      return (P() + rev(A) + query(1, dfn[a], dfn[b]) + B + P()).v;
    }
  }
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; ++i) scanf("%d", &F[i]);
  for (int i = 1; i < n; ++i) {
    scanf("%d%d%d", &Ut[i], &Vt[i], &Wt[i]);
    B[Ut[i]].push_back(i + n);
    B[i + n].push_back(Ut[i]);
    B[Vt[i]].push_back(i + n);
    B[i + n].push_back(Vt[i]);
  }
  for (int i = 1; i <= q; ++i) scanf("%d%d%d", &Uq[i], &Vq[i], &Wq[i]);
  for (int i = 1; i < n; ++i) ordt[i] = i;
  sort(ordt + 1, ordt + n, [](int a, int b) { return Wt[a] > Wt[b]; });
  for (int i = 1; i <= q; ++i) ordq[i] = i;
  sort(ordq + 1, ordq + q + 1, [](int a, int b) { return Wq[a] > Wq[b]; });
  dfs1();
  dfs2();
  build(1, n + n - 1);
  for (int i = 1, j = 1; i <= q; ++i) {
    while (j < n && Wt[ordt[j]] >= Wq[ordq[i]]) {
      modify(1, dfn[ordt[j] + n]);
      j++;
    }
    res[ordq[i]] = query(Uq[ordq[i]], Vq[ordq[i]]);
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", res[i]);
}

```