#include <bits/stdc++.h>
using namespace std;
const int mn = 2e5 + 8;
typedef int arr[mn];
int n, q, idx;
pair<int, int> a[mn];
arr f, dfn, fa, ms, siz, dep, last, top;
struct Edge {
  Edge *n;
  int v;
} * h[mn];
void AddEdge(int u, int v) {
  Edge *x = new Edge();
  x->v = v;
  x->n = h[u];
  h[u] = x;
}
struct Info {
  int ml, mr, v, s;
  Info(int _v = 0) {
    ml = mr = v = _v;
    s = 0;
  }
  Info(int ml, int mr, int v, int s) : ml(ml), mr(mr), v(v), s(s) {}
  Info operator+=(const Info &o) {
    if (mr != v && o.ml != o.v) s += f[mr + o.ml];
    mr = o.mr == o.v ? o.v + mr : o.mr;
    ml = ml == v ? v + o.ml : ml;
    v += o.v;
    s += o.s;
    return *this;
  }
  Info operator+(const Info &o) const {
    Info r = *this;
    return r += o;
  }
};
struct Query {
  int u, v, l, o;
  bool operator<(const Query o) const { return l < o.l; }
} Q[mn];
struct Node {
  Node *c[2];
  Info d;
  Node(int v = 0) {
    c[0] = c[1] = NULL;
    d = Info(v);
  }
  void mt() { d = c[0]->d + c[1]->d; }
} * rt[mn];
Node *Build(int l, int r) {
  Node *x = new Node(r - l + 1);
  if (l != r) {
    int m = l + r >> 1;
    x->c[0] = Build(l, m);
    x->c[1] = Build(m + 1, r);
  }
  return x;
}
void Modify(Node *x, int l, int r, int p) {
  if (l == r)
    x->d = Info(0, 0, 1, 0);
  else {
    int m = l + r >> 1;
    if (p <= m)
      Modify(x->c[0], l, m, p);
    else
      Modify(x->c[1], m + 1, r, p);
    x->mt();
  }
}
Info Count(Node *x, int l, int r, int s, int t) {
  if (l > t || r < s) return Info();
  if (l >= s && r <= t) return x->d;
  int m = l + r >> 1;
  return Count(x->c[0], l, m, s, t) + Count(x->c[1], m + 1, r, s, t);
}
void Prepare(int u) {
  siz[u] = 1;
  ms[u] = -1;
  pair<int, int> t = make_pair(-1, -1);
  for (Edge *e = h[u]; e; e = e->n)
    if (e->v != fa[u]) {
      fa[e->v] = u;
      dep[e->v] = dep[u] + 1;
      Prepare(e->v);
      siz[u] += siz[e->v];
      t = max(t, make_pair(siz[e->v], e->v));
    }
  ms[u] = t.second;
}
void Tour(int u) {
  dfn[u] = ++idx;
  top[u] = ms[fa[u]] == u ? top[fa[u]] : u;
  for (Edge *e = h[u]; e; e = e->n)
    if (e->v != fa[u])
      if (e->v == ms[u]) Tour(e->v);
  for (Edge *e = h[u]; e; e = e->n)
    if (e->v != fa[u])
      if (e->v != ms[u]) Tour(e->v);
  if (ms[u] == -1)
    rt[top[u]] = Build(dfn[top[u]], dfn[last[u] = u]);
  else
    last[u] = last[ms[u]];
}
void Reverse(int x) { Modify(rt[top[x]], dfn[top[x]], dfn[last[x]], dfn[x]); }
int Ask(int u, int v) {
  Info du, dv;
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v), swap(du, dv);
    du = Count(rt[top[u]], dfn[top[u]], dfn[last[u]], dfn[top[u]], dfn[u]) + du;
    u = fa[top[u]];
  }
  if (dep[u] < dep[v]) swap(u, v), swap(du, dv);
  swap(dv.ml, dv.mr);
  du = dv + Count(rt[top[u]], dfn[top[u]], dfn[last[u]], dfn[v], dfn[u]) + du;
  return du.s + (du.v == du.mr ? f[du.ml] : f[du.ml] + f[du.mr]);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; i++) scanf("%d", f + (i << 1 | 1));
  for (int i = 1; i < n; i++) {
    int u, v, d;
    scanf("%d%d%d", &u, &v, &d);
    a[i - 1] = make_pair(d, n + i);
    AddEdge(u, n + i);
    AddEdge(n + i, u);
    AddEdge(v, n + i);
    AddEdge(n + i, v);
  }
  sort(a, a + n - 1);
  Prepare(dep[1] = 1);
  Tour(1);
  for (int i = 0; i < q; i++)
    scanf("%d%d%d", &Q[i].u, &Q[i].v, &Q[i].l), Q[i].o = i;
  sort(Q, Q + q);
  int top = 0;
  static arr ans;
  for (int i = 0; i < q; i++) {
    while (top < n - 1 && a[top].first < Q[i].l) Reverse(a[top++].second);
    ans[Q[i].o] = Ask(Q[i].u, Q[i].v);
  }
  for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
  fclose(stdin);
  fclose(stdout);
  return 0;
}

### Prompt

Generate 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 mn = 2e5 + 8;
typedef int arr[mn];
int n, q, idx;
pair<int, int> a[mn];
arr f, dfn, fa, ms, siz, dep, last, top;
struct Edge {
  Edge *n;
  int v;
} * h[mn];
void AddEdge(int u, int v) {
  Edge *x = new Edge();
  x->v = v;
  x->n = h[u];
  h[u] = x;
}
struct Info {
  int ml, mr, v, s;
  Info(int _v = 0) {
    ml = mr = v = _v;
    s = 0;
  }
  Info(int ml, int mr, int v, int s) : ml(ml), mr(mr), v(v), s(s) {}
  Info operator+=(const Info &o) {
    if (mr != v && o.ml != o.v) s += f[mr + o.ml];
    mr = o.mr == o.v ? o.v + mr : o.mr;
    ml = ml == v ? v + o.ml : ml;
    v += o.v;
    s += o.s;
    return *this;
  }
  Info operator+(const Info &o) const {
    Info r = *this;
    return r += o;
  }
};
struct Query {
  int u, v, l, o;
  bool operator<(const Query o) const { return l < o.l; }
} Q[mn];
struct Node {
  Node *c[2];
  Info d;
  Node(int v = 0) {
    c[0] = c[1] = NULL;
    d = Info(v);
  }
  void mt() { d = c[0]->d + c[1]->d; }
} * rt[mn];
Node *Build(int l, int r) {
  Node *x = new Node(r - l + 1);
  if (l != r) {
    int m = l + r >> 1;
    x->c[0] = Build(l, m);
    x->c[1] = Build(m + 1, r);
  }
  return x;
}
void Modify(Node *x, int l, int r, int p) {
  if (l == r)
    x->d = Info(0, 0, 1, 0);
  else {
    int m = l + r >> 1;
    if (p <= m)
      Modify(x->c[0], l, m, p);
    else
      Modify(x->c[1], m + 1, r, p);
    x->mt();
  }
}
Info Count(Node *x, int l, int r, int s, int t) {
  if (l > t || r < s) return Info();
  if (l >= s && r <= t) return x->d;
  int m = l + r >> 1;
  return Count(x->c[0], l, m, s, t) + Count(x->c[1], m + 1, r, s, t);
}
void Prepare(int u) {
  siz[u] = 1;
  ms[u] = -1;
  pair<int, int> t = make_pair(-1, -1);
  for (Edge *e = h[u]; e; e = e->n)
    if (e->v != fa[u]) {
      fa[e->v] = u;
      dep[e->v] = dep[u] + 1;
      Prepare(e->v);
      siz[u] += siz[e->v];
      t = max(t, make_pair(siz[e->v], e->v));
    }
  ms[u] = t.second;
}
void Tour(int u) {
  dfn[u] = ++idx;
  top[u] = ms[fa[u]] == u ? top[fa[u]] : u;
  for (Edge *e = h[u]; e; e = e->n)
    if (e->v != fa[u])
      if (e->v == ms[u]) Tour(e->v);
  for (Edge *e = h[u]; e; e = e->n)
    if (e->v != fa[u])
      if (e->v != ms[u]) Tour(e->v);
  if (ms[u] == -1)
    rt[top[u]] = Build(dfn[top[u]], dfn[last[u] = u]);
  else
    last[u] = last[ms[u]];
}
void Reverse(int x) { Modify(rt[top[x]], dfn[top[x]], dfn[last[x]], dfn[x]); }
int Ask(int u, int v) {
  Info du, dv;
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v), swap(du, dv);
    du = Count(rt[top[u]], dfn[top[u]], dfn[last[u]], dfn[top[u]], dfn[u]) + du;
    u = fa[top[u]];
  }
  if (dep[u] < dep[v]) swap(u, v), swap(du, dv);
  swap(dv.ml, dv.mr);
  du = dv + Count(rt[top[u]], dfn[top[u]], dfn[last[u]], dfn[v], dfn[u]) + du;
  return du.s + (du.v == du.mr ? f[du.ml] : f[du.ml] + f[du.mr]);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; i++) scanf("%d", f + (i << 1 | 1));
  for (int i = 1; i < n; i++) {
    int u, v, d;
    scanf("%d%d%d", &u, &v, &d);
    a[i - 1] = make_pair(d, n + i);
    AddEdge(u, n + i);
    AddEdge(n + i, u);
    AddEdge(v, n + i);
    AddEdge(n + i, v);
  }
  sort(a, a + n - 1);
  Prepare(dep[1] = 1);
  Tour(1);
  for (int i = 0; i < q; i++)
    scanf("%d%d%d", &Q[i].u, &Q[i].v, &Q[i].l), Q[i].o = i;
  sort(Q, Q + q);
  int top = 0;
  static arr ans;
  for (int i = 0; i < q; i++) {
    while (top < n - 1 && a[top].first < Q[i].l) Reverse(a[top++].second);
    ans[Q[i].o] = Ask(Q[i].u, Q[i].v);
  }
  for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
  fclose(stdin);
  fclose(stdout);
  return 0;
}

```