#include <bits/stdc++.h>
using namespace std;
int n, q, head[200200], ans[200200], cnt, top[200200], L[200200], Clk,
    son[200200], dep[200200], f[200200], idx[200200], siz[200200], Len[200200],
    Fa[200200];
struct data {
  int idx, u, v, w;
  bool operator<(const data &rhs) const { return w < rhs.w; }
  void read() { scanf("%d%d%d", &u, &v, &w); }
} ed[200200], qy[200200];
struct Edge {
  int to, next, cost;
} edge[200200 << 1];
void AddEdge(int u, int v, int w) {
  edge[++cnt] = (Edge){v, head[u], w};
  head[u] = cnt;
  edge[++cnt] = (Edge){u, head[v], w};
  head[v] = cnt;
}
void Dfs(int u, int fa) {
  dep[u] = dep[fa] + 1;
  Fa[u] = fa;
  for (int i = head[u]; i; i = edge[i].next) {
    int v = edge[i].to;
    if (v == fa) continue;
    Dfs(v, u);
    siz[u] += siz[v];
    if (siz[v] > siz[son[u]]) son[u] = v;
  }
  siz[u]++;
}
void Dfs(int u, int fa, int tp) {
  L[u] = ++Clk;
  idx[u] = ++Len[top[u] = tp];
  if (son[u]) Dfs(son[u], u, tp);
  for (int i = head[u]; i; i = edge[i].next) {
    int v = edge[i].to;
    if (v == fa || v == son[u]) continue;
    Dfs(v, u, v);
  }
}
struct Node {
  int Ln, Rn, Tc, l;
  Node() { Ln = Rn = Tc = l = 0; }
} tree[200200 << 2];
void Merge(Node &rt, Node ls, Node rs) {
  rt.l = ls.l + rs.l;
  rt.Ln = ls.Ln;
  if (ls.Ln == ls.l) rt.Ln += rs.Ln;
  rt.Rn = rs.Rn;
  if (rs.Rn == rs.l) rt.Rn += ls.Rn;
  rt.Tc = ls.Tc + rs.Tc - f[ls.Rn] - f[rs.Ln] + f[ls.Rn + rs.Ln];
}
void Build(int rt, int l, int r) {
  if (l == r) {
    if (l ^ 1) tree[rt].l = tree[rt].Ln = tree[rt].Rn = 1, tree[rt].Tc = f[1];
    return;
  }
  Build(rt << 1, l, ((l + r) >> 1));
  Build(rt << 1 | 1, ((l + r) >> 1) + 1, r);
  Merge(tree[rt], tree[rt << 1], tree[rt << 1 | 1]);
}
void Update(int rt, int l, int r, int p) {
  if (l == r) {
    tree[rt].Ln = tree[rt].Rn = tree[rt].Tc = 0;
    return;
  }
  if (p <= ((l + r) >> 1))
    Update(rt << 1, l, ((l + r) >> 1), p);
  else
    Update(rt << 1 | 1, ((l + r) >> 1) + 1, r, p);
  Merge(tree[rt], tree[rt << 1], tree[rt << 1 | 1]);
}
Node Query(int rt, int l, int r, int L, int R) {
  if (l >= L && r <= R) return tree[rt];
  Node ret;
  if (L <= ((l + r) >> 1)) ret = Query(rt << 1, l, ((l + r) >> 1), L, R);
  if (R > ((l + r) >> 1))
    Merge(ret, ret, Query(rt << 1 | 1, ((l + r) >> 1) + 1, r, L, R));
  return ret;
}
int Query(int u, int v) {
  Node la, ra, tmp;
  while (top[u] != top[v]) {
    if (dep[top[u]] > dep[top[v]]) {
      tmp = Query(1, 1, n, L[top[u]], L[u]);
      swap(tmp.Ln, tmp.Rn);
      Merge(tmp, la, tmp);
      la = tmp;
      u = Fa[top[u]];
    } else {
      tmp = Query(1, 1, n, L[top[v]], L[v]);
      Merge(tmp, tmp, ra);
      ra = tmp;
      v = Fa[top[v]];
    }
  }
  if (u == v) {
    Merge(tmp, la, ra);
    return tmp.Tc;
  }
  if (dep[u] > dep[v]) {
    tmp = Query(1, 1, n, L[v] + 1, L[u]);
    swap(tmp.Ln, tmp.Rn);
    Merge(tmp, la, tmp);
    la = tmp;
    Merge(tmp, la, ra);
    return tmp.Tc;
  } else {
    tmp = Query(1, 1, n, L[u] + 1, L[v]);
    Merge(tmp, la, tmp);
    la = tmp;
    Merge(tmp, la, ra);
    return tmp.Tc;
  }
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n - 1; i++) scanf("%d", f + i);
  for (int i = 1; i <= n - 1; i++)
    ed[i].read(), AddEdge(ed[i].u, ed[i].v, ed[i].w);
  for (int i = 1; i <= q; i++) qy[i].read(), qy[i].idx = i;
  sort(ed + 1, ed + n);
  sort(qy + 1, qy + q + 1);
  Dfs(1, 0), Dfs(1, 0, 1);
  Build(1, 1, n);
  int k = 1;
  for (int i = 1, j; i < n; i = j) {
    j = i;
    while (k <= q && qy[k].w <= ed[i].w)
      ans[qy[k].idx] = Query(qy[k].u, qy[k].v), k++;
    while (j < n && ed[i].w == ed[j].w)
      Update(1, 1, n, max(L[ed[j].u], L[ed[j].v])), j++;
  }
  for (; k <= q; k++) ans[qy[k].idx] = 0;
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}

### 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;
int n, q, head[200200], ans[200200], cnt, top[200200], L[200200], Clk,
    son[200200], dep[200200], f[200200], idx[200200], siz[200200], Len[200200],
    Fa[200200];
struct data {
  int idx, u, v, w;
  bool operator<(const data &rhs) const { return w < rhs.w; }
  void read() { scanf("%d%d%d", &u, &v, &w); }
} ed[200200], qy[200200];
struct Edge {
  int to, next, cost;
} edge[200200 << 1];
void AddEdge(int u, int v, int w) {
  edge[++cnt] = (Edge){v, head[u], w};
  head[u] = cnt;
  edge[++cnt] = (Edge){u, head[v], w};
  head[v] = cnt;
}
void Dfs(int u, int fa) {
  dep[u] = dep[fa] + 1;
  Fa[u] = fa;
  for (int i = head[u]; i; i = edge[i].next) {
    int v = edge[i].to;
    if (v == fa) continue;
    Dfs(v, u);
    siz[u] += siz[v];
    if (siz[v] > siz[son[u]]) son[u] = v;
  }
  siz[u]++;
}
void Dfs(int u, int fa, int tp) {
  L[u] = ++Clk;
  idx[u] = ++Len[top[u] = tp];
  if (son[u]) Dfs(son[u], u, tp);
  for (int i = head[u]; i; i = edge[i].next) {
    int v = edge[i].to;
    if (v == fa || v == son[u]) continue;
    Dfs(v, u, v);
  }
}
struct Node {
  int Ln, Rn, Tc, l;
  Node() { Ln = Rn = Tc = l = 0; }
} tree[200200 << 2];
void Merge(Node &rt, Node ls, Node rs) {
  rt.l = ls.l + rs.l;
  rt.Ln = ls.Ln;
  if (ls.Ln == ls.l) rt.Ln += rs.Ln;
  rt.Rn = rs.Rn;
  if (rs.Rn == rs.l) rt.Rn += ls.Rn;
  rt.Tc = ls.Tc + rs.Tc - f[ls.Rn] - f[rs.Ln] + f[ls.Rn + rs.Ln];
}
void Build(int rt, int l, int r) {
  if (l == r) {
    if (l ^ 1) tree[rt].l = tree[rt].Ln = tree[rt].Rn = 1, tree[rt].Tc = f[1];
    return;
  }
  Build(rt << 1, l, ((l + r) >> 1));
  Build(rt << 1 | 1, ((l + r) >> 1) + 1, r);
  Merge(tree[rt], tree[rt << 1], tree[rt << 1 | 1]);
}
void Update(int rt, int l, int r, int p) {
  if (l == r) {
    tree[rt].Ln = tree[rt].Rn = tree[rt].Tc = 0;
    return;
  }
  if (p <= ((l + r) >> 1))
    Update(rt << 1, l, ((l + r) >> 1), p);
  else
    Update(rt << 1 | 1, ((l + r) >> 1) + 1, r, p);
  Merge(tree[rt], tree[rt << 1], tree[rt << 1 | 1]);
}
Node Query(int rt, int l, int r, int L, int R) {
  if (l >= L && r <= R) return tree[rt];
  Node ret;
  if (L <= ((l + r) >> 1)) ret = Query(rt << 1, l, ((l + r) >> 1), L, R);
  if (R > ((l + r) >> 1))
    Merge(ret, ret, Query(rt << 1 | 1, ((l + r) >> 1) + 1, r, L, R));
  return ret;
}
int Query(int u, int v) {
  Node la, ra, tmp;
  while (top[u] != top[v]) {
    if (dep[top[u]] > dep[top[v]]) {
      tmp = Query(1, 1, n, L[top[u]], L[u]);
      swap(tmp.Ln, tmp.Rn);
      Merge(tmp, la, tmp);
      la = tmp;
      u = Fa[top[u]];
    } else {
      tmp = Query(1, 1, n, L[top[v]], L[v]);
      Merge(tmp, tmp, ra);
      ra = tmp;
      v = Fa[top[v]];
    }
  }
  if (u == v) {
    Merge(tmp, la, ra);
    return tmp.Tc;
  }
  if (dep[u] > dep[v]) {
    tmp = Query(1, 1, n, L[v] + 1, L[u]);
    swap(tmp.Ln, tmp.Rn);
    Merge(tmp, la, tmp);
    la = tmp;
    Merge(tmp, la, ra);
    return tmp.Tc;
  } else {
    tmp = Query(1, 1, n, L[u] + 1, L[v]);
    Merge(tmp, la, tmp);
    la = tmp;
    Merge(tmp, la, ra);
    return tmp.Tc;
  }
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n - 1; i++) scanf("%d", f + i);
  for (int i = 1; i <= n - 1; i++)
    ed[i].read(), AddEdge(ed[i].u, ed[i].v, ed[i].w);
  for (int i = 1; i <= q; i++) qy[i].read(), qy[i].idx = i;
  sort(ed + 1, ed + n);
  sort(qy + 1, qy + q + 1);
  Dfs(1, 0), Dfs(1, 0, 1);
  Build(1, 1, n);
  int k = 1;
  for (int i = 1, j; i < n; i = j) {
    j = i;
    while (k <= q && qy[k].w <= ed[i].w)
      ans[qy[k].idx] = Query(qy[k].u, qy[k].v), k++;
    while (j < n && ed[i].w == ed[j].w)
      Update(1, 1, n, max(L[ed[j].u], L[ed[j].v])), j++;
  }
  for (; k <= q; k++) ans[qy[k].idx] = 0;
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}

```