#include <bits/stdc++.h>
using namespace std;
int n, a[100005], ans[100005];
struct edge {
  int u, v, w, pre;
} e[200005];
int dex, adj[100005];
struct Ques {
  int x, y, v, id;
} Q[100005];
int tQ;
int fa[100005], dep[100005], hev[100005], sz[100005], top[100005];
int dfn[100005], Ind[100005], ttt;
struct Info {
  int lx, rx, sm, len;
  inline Info operator+(const Info &A) const {
    if (!len) return A;
    if (!A.len) return *this;
    Info res = *this;
    res.len += A.len;
    if (lx == len && rx == len && A.lx == A.len && A.rx == A.len) {
      res.lx = res.rx = res.len;
      res.sm = 0;
      return res;
    }
    if (A.lx == A.len && A.rx == A.len) {
      res.rx = A.len + rx;
      res.lx = lx;
      res.sm = sm;
      return res;
    }
    if (lx == len && rx == len) {
      res.lx = len + A.lx;
      res.rx = A.rx;
      res.sm = A.sm;
      return res;
    }
    res.lx = lx;
    res.rx = A.rx;
    res.sm = sm + A.sm + a[rx + A.lx];
    return res;
  }
} t[400005], resL, resR;
int all[400005];
inline int operator<(const Ques &A, const Ques &B) { return A.v > B.v; }
inline int operator<(const edge &A, const edge &B) { return A.w > B.w; }
void dfs(int x) {
  for (int i = adj[x]; i; i = e[i].pre) {
    int v = e[i].v;
    if (v == fa[x]) continue;
    fa[v] = x;
    dep[v] = dep[x] + 1;
    dfs(v);
    sz[x] += sz[v];
    if (sz[v] > sz[hev[x]]) hev[x] = v;
  }
  ++sz[x];
}
void build(int x) {
  dfn[x] = ++ttt;
  Ind[ttt] = x;
  if (hev[x]) {
    top[hev[x]] = top[x];
    build(hev[x]);
  }
  for (int i = adj[x]; i; i = e[i].pre) {
    int v = e[i].v;
    if (v == fa[x]) continue;
    if (v == hev[x]) continue;
    top[v] = v;
    build(v);
  }
}
void Mod(int x, int L, int R, int v) {
  if (L == R) {
    t[x].lx = t[x].rx = t[x].len = 1;
    t[x].sm = 0;
    return;
  }
  int md = (L + R) >> 1;
  if (v <= md)
    Mod(x * 2, L, md, v);
  else
    Mod(x * 2 + 1, md + 1, R, v);
  if (all[x]) t[x] = t[x * 2] + t[x * 2 + 1];
}
void build_tree(int x, int L, int R) {
  if (L == R) {
    t[x].len = 1;
    t[x].lx = t[x].rx = 0;
    t[x].sm = 0;
    all[x] = top[Ind[L]];
    return;
  }
  int md = (L + R) >> 1;
  build_tree(x * 2, L, md);
  build_tree(x * 2 + 1, md + 1, R);
  if (all[x * 2] == all[x * 2 + 1] && all[x * 2] > 0)
    all[x] = all[x * 2];
  else
    all[x] = 0;
  if (all[x]) t[x] = t[x * 2] + t[x * 2 + 1];
}
Info ask(int x, int L, int R, int ll, int rr) {
  if (ll <= L && R <= rr) return t[x];
  if (ll > rr) return (Info){0, 0, 0, 0};
  int md = (L + R) >> 1;
  Info res = (Info){0, 0, 0, 0};
  if (ll <= md) res = res + ask(x * 2, L, md, ll, rr);
  if (md < rr) res = res + ask(x * 2 + 1, md + 1, R, ll, rr);
  return res;
}
int ask(int x, int y) {
  resL.len = resL.lx = resL.rx = resL.sm = 0;
  resR.len = resR.lx = resR.rx = resR.sm = 0;
  for (; top[x] ^ top[y];) {
    if (dep[top[x]] < dep[top[y]]) {
      resR = ask(1, 1, n, dfn[top[y]], dfn[y]) + resR;
      y = fa[top[y]];
    } else {
      Info tmp = ask(1, 1, n, dfn[top[x]], dfn[x]);
      swap(tmp.lx, tmp.rx);
      resL = resL + tmp;
      x = fa[top[x]];
    }
  }
  if (dep[x] <= dep[y]) {
    resL = resL + ask(1, 1, n, dfn[x] + 1, dfn[y]) + resR;
    if (resL.lx == resL.len && resL.rx == resL.len) return a[resL.lx];
    return a[resL.lx] + a[resL.rx] + resL.sm;
  } else {
    Info tmp = ask(1, 1, n, dfn[y] + 1, dfn[x]);
    swap(tmp.lx, tmp.rx);
    resR = resL + tmp + resR;
    if (resR.lx == resR.len && resR.rx == resR.len) return a[resR.lx];
    return a[resR.lx] + a[resR.rx] + resR.sm;
  }
}
int main() {
  scanf("%d%d", &n, &tQ);
  for (int i = 1; i <= n - 1; i++) scanf("%d", a + i);
  for (int i = 1; i <= n - 1; i++) {
    int x, y, w;
    scanf("%d%d%d", &x, &y, &w);
    e[++dex] = (edge){x, y, w, adj[x]};
    adj[x] = dex;
    e[++dex] = (edge){y, x, w, adj[y]};
    adj[y] = dex;
  }
  for (int i = 1; i <= tQ; i++) {
    scanf("%d%d%d", &Q[i].x, &Q[i].y, &Q[i].v);
    Q[i].id = i;
  }
  dep[1] = top[1] = 1;
  dfs(1);
  build(1);
  build_tree(1, 1, n);
  sort(Q + 1, Q + tQ + 1);
  sort(e + 1, e + dex + 1);
  int now = 1;
  for (int i = 1; i <= tQ; i++) {
    while (now <= dex && e[now].w >= Q[i].v) {
      if (dep[e[now].u] < dep[e[now].v]) Mod(1, 1, n, dfn[e[now].v]);
      ++now;
    }
    ans[Q[i].id] = ask(Q[i].x, Q[i].y);
  }
  for (int i = 1; i <= tQ; i++) printf("%d\n", ans[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;
int n, a[100005], ans[100005];
struct edge {
  int u, v, w, pre;
} e[200005];
int dex, adj[100005];
struct Ques {
  int x, y, v, id;
} Q[100005];
int tQ;
int fa[100005], dep[100005], hev[100005], sz[100005], top[100005];
int dfn[100005], Ind[100005], ttt;
struct Info {
  int lx, rx, sm, len;
  inline Info operator+(const Info &A) const {
    if (!len) return A;
    if (!A.len) return *this;
    Info res = *this;
    res.len += A.len;
    if (lx == len && rx == len && A.lx == A.len && A.rx == A.len) {
      res.lx = res.rx = res.len;
      res.sm = 0;
      return res;
    }
    if (A.lx == A.len && A.rx == A.len) {
      res.rx = A.len + rx;
      res.lx = lx;
      res.sm = sm;
      return res;
    }
    if (lx == len && rx == len) {
      res.lx = len + A.lx;
      res.rx = A.rx;
      res.sm = A.sm;
      return res;
    }
    res.lx = lx;
    res.rx = A.rx;
    res.sm = sm + A.sm + a[rx + A.lx];
    return res;
  }
} t[400005], resL, resR;
int all[400005];
inline int operator<(const Ques &A, const Ques &B) { return A.v > B.v; }
inline int operator<(const edge &A, const edge &B) { return A.w > B.w; }
void dfs(int x) {
  for (int i = adj[x]; i; i = e[i].pre) {
    int v = e[i].v;
    if (v == fa[x]) continue;
    fa[v] = x;
    dep[v] = dep[x] + 1;
    dfs(v);
    sz[x] += sz[v];
    if (sz[v] > sz[hev[x]]) hev[x] = v;
  }
  ++sz[x];
}
void build(int x) {
  dfn[x] = ++ttt;
  Ind[ttt] = x;
  if (hev[x]) {
    top[hev[x]] = top[x];
    build(hev[x]);
  }
  for (int i = adj[x]; i; i = e[i].pre) {
    int v = e[i].v;
    if (v == fa[x]) continue;
    if (v == hev[x]) continue;
    top[v] = v;
    build(v);
  }
}
void Mod(int x, int L, int R, int v) {
  if (L == R) {
    t[x].lx = t[x].rx = t[x].len = 1;
    t[x].sm = 0;
    return;
  }
  int md = (L + R) >> 1;
  if (v <= md)
    Mod(x * 2, L, md, v);
  else
    Mod(x * 2 + 1, md + 1, R, v);
  if (all[x]) t[x] = t[x * 2] + t[x * 2 + 1];
}
void build_tree(int x, int L, int R) {
  if (L == R) {
    t[x].len = 1;
    t[x].lx = t[x].rx = 0;
    t[x].sm = 0;
    all[x] = top[Ind[L]];
    return;
  }
  int md = (L + R) >> 1;
  build_tree(x * 2, L, md);
  build_tree(x * 2 + 1, md + 1, R);
  if (all[x * 2] == all[x * 2 + 1] && all[x * 2] > 0)
    all[x] = all[x * 2];
  else
    all[x] = 0;
  if (all[x]) t[x] = t[x * 2] + t[x * 2 + 1];
}
Info ask(int x, int L, int R, int ll, int rr) {
  if (ll <= L && R <= rr) return t[x];
  if (ll > rr) return (Info){0, 0, 0, 0};
  int md = (L + R) >> 1;
  Info res = (Info){0, 0, 0, 0};
  if (ll <= md) res = res + ask(x * 2, L, md, ll, rr);
  if (md < rr) res = res + ask(x * 2 + 1, md + 1, R, ll, rr);
  return res;
}
int ask(int x, int y) {
  resL.len = resL.lx = resL.rx = resL.sm = 0;
  resR.len = resR.lx = resR.rx = resR.sm = 0;
  for (; top[x] ^ top[y];) {
    if (dep[top[x]] < dep[top[y]]) {
      resR = ask(1, 1, n, dfn[top[y]], dfn[y]) + resR;
      y = fa[top[y]];
    } else {
      Info tmp = ask(1, 1, n, dfn[top[x]], dfn[x]);
      swap(tmp.lx, tmp.rx);
      resL = resL + tmp;
      x = fa[top[x]];
    }
  }
  if (dep[x] <= dep[y]) {
    resL = resL + ask(1, 1, n, dfn[x] + 1, dfn[y]) + resR;
    if (resL.lx == resL.len && resL.rx == resL.len) return a[resL.lx];
    return a[resL.lx] + a[resL.rx] + resL.sm;
  } else {
    Info tmp = ask(1, 1, n, dfn[y] + 1, dfn[x]);
    swap(tmp.lx, tmp.rx);
    resR = resL + tmp + resR;
    if (resR.lx == resR.len && resR.rx == resR.len) return a[resR.lx];
    return a[resR.lx] + a[resR.rx] + resR.sm;
  }
}
int main() {
  scanf("%d%d", &n, &tQ);
  for (int i = 1; i <= n - 1; i++) scanf("%d", a + i);
  for (int i = 1; i <= n - 1; i++) {
    int x, y, w;
    scanf("%d%d%d", &x, &y, &w);
    e[++dex] = (edge){x, y, w, adj[x]};
    adj[x] = dex;
    e[++dex] = (edge){y, x, w, adj[y]};
    adj[y] = dex;
  }
  for (int i = 1; i <= tQ; i++) {
    scanf("%d%d%d", &Q[i].x, &Q[i].y, &Q[i].v);
    Q[i].id = i;
  }
  dep[1] = top[1] = 1;
  dfs(1);
  build(1);
  build_tree(1, 1, n);
  sort(Q + 1, Q + tQ + 1);
  sort(e + 1, e + dex + 1);
  int now = 1;
  for (int i = 1; i <= tQ; i++) {
    while (now <= dex && e[now].w >= Q[i].v) {
      if (dep[e[now].u] < dep[e[now].v]) Mod(1, 1, n, dfn[e[now].v]);
      ++now;
    }
    ans[Q[i].id] = ask(Q[i].x, Q[i].y);
  }
  for (int i = 1; i <= tQ; i++) printf("%d\n", ans[i]);
  return 0;
}

```