#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int size[N], son[N], dep[N], fa[N], top[N], mark[N], tot;
int F[N], fw[N], id[N], ans[N], n, q;
vector<int> G[N];
vector<int> W[N];
void dfs1(int x, int f) {
  id[x] = x;
  size[x] = 1;
  fa[x] = f;
  dep[x] = dep[f] + 1;
  int m = 0;
  for (int i = 0; i < G[x].size(); i++) {
    int u = G[x][i];
    if (f != u) {
      fw[u] = W[x][i];
      dfs1(u, x);
      size[x] += size[u];
      if (size[u] > size[m]) m = u;
    }
  }
  son[x] = m;
}
void dfs2(int x, int f) {
  if (son[x] != 0) {
    tot++;
    top[son[x]] = top[x];
    mark[son[x]] = tot;
    dfs2(son[x], x);
  }
  for (int u : G[x]) {
    if (u != f && u != son[x]) {
      tot++;
      top[u] = u;
      mark[u] = tot;
      dfs2(u, x);
    }
  }
}
bool cmp(int i, int j) { return fw[i] > fw[j]; }
struct event {
  int u, v, l, id;
  event() {}
  void input() { scanf("%d %d %d", &u, &v, &l); }
  bool operator<(const event &a) const { return l > a.l; }
} Q[N];
struct info {
  int val, le, ri, len;
  info() {}
  void clear() { len = val = le = ri = 0; }
} a[N * 4];
void build(int k, int l, int r) {
  a[k].clear();
  a[k].len = r - l + 1;
  if (l == r) return;
  int mid = l + r >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
}
inline info merge(const info &a, const info &b) {
  info res;
  res.len = a.len + b.len;
  res.val = a.val + b.val;
  if (a.ri && b.le) {
    res.val -= F[a.ri] + F[b.le];
    res.val += F[a.ri + b.le];
  }
  res.le = a.le;
  if (a.le == a.len) res.le += b.le;
  res.ri = b.ri;
  if (b.ri == b.len) res.ri += a.ri;
  return res;
}
void modify(int k, int l, int r, int p) {
  if (l == r) {
    a[k].le = a[k].ri = 1;
    a[k].val = F[1];
    return;
  }
  int mid = l + r >> 1;
  if (p <= mid)
    modify(k << 1, l, mid, p);
  else
    modify(k << 1 | 1, mid + 1, r, p);
  a[k] = merge(a[k << 1], a[k << 1 | 1]);
}
info Query(int k, int l, int r, int p, int q) {
  if (l >= p && r <= q) return a[k];
  int mid = l + r >> 1;
  if (mid >= q) return Query(k << 1, l, mid, p, q);
  if (mid + 1 <= p) return Query(k << 1 | 1, mid + 1, r, p, q);
  return merge(Query(k << 1, l, mid, p, q),
               Query(k << 1 | 1, mid + 1, r, p, q));
}
info work(int x, int y) {
  info a, b;
  a.clear();
  b.clear();
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]]) {
      a = merge(Query(1, 1, n, mark[top[x]], mark[x]), a);
      x = fa[top[x]];
    } else {
      b = merge(Query(1, 1, n, mark[top[y]], mark[y]), b);
      y = fa[top[y]];
    }
  }
  if (dep[x] > dep[y]) {
    a = merge(Query(1, 1, n, mark[y] + 1, mark[x]), a);
  }
  if (dep[y] > dep[x]) {
    b = merge(Query(1, 1, n, mark[x] + 1, mark[y]), b);
  }
  swap(a.le, a.ri);
  return merge(a, b);
}
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++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    G[u].push_back(v);
    G[v].push_back(u);
    W[u].push_back(w);
    W[v].push_back(w);
  }
  fw[1] = -2e9;
  for (int i = 1; i <= q; i++) {
    Q[i].input();
    Q[i].id = i;
  }
  sort(Q + 1, Q + 1 + q);
  dfs1(1, 0);
  top[1] = 1;
  tot = 1;
  mark[1] = 1;
  dfs2(1, 0);
  build(1, 1, n);
  int p = 1;
  sort(id + 1, id + 1 + n, cmp);
  for (int i = 1; i <= q; i++) {
    while (p < n && fw[id[p]] >= Q[i].l) {
      modify(1, 1, n, mark[id[p]]);
      p++;
    }
    info res = work(Q[i].u, Q[i].v);
    ans[Q[i].id] = res.val;
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[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 = 2e5 + 5;
int size[N], son[N], dep[N], fa[N], top[N], mark[N], tot;
int F[N], fw[N], id[N], ans[N], n, q;
vector<int> G[N];
vector<int> W[N];
void dfs1(int x, int f) {
  id[x] = x;
  size[x] = 1;
  fa[x] = f;
  dep[x] = dep[f] + 1;
  int m = 0;
  for (int i = 0; i < G[x].size(); i++) {
    int u = G[x][i];
    if (f != u) {
      fw[u] = W[x][i];
      dfs1(u, x);
      size[x] += size[u];
      if (size[u] > size[m]) m = u;
    }
  }
  son[x] = m;
}
void dfs2(int x, int f) {
  if (son[x] != 0) {
    tot++;
    top[son[x]] = top[x];
    mark[son[x]] = tot;
    dfs2(son[x], x);
  }
  for (int u : G[x]) {
    if (u != f && u != son[x]) {
      tot++;
      top[u] = u;
      mark[u] = tot;
      dfs2(u, x);
    }
  }
}
bool cmp(int i, int j) { return fw[i] > fw[j]; }
struct event {
  int u, v, l, id;
  event() {}
  void input() { scanf("%d %d %d", &u, &v, &l); }
  bool operator<(const event &a) const { return l > a.l; }
} Q[N];
struct info {
  int val, le, ri, len;
  info() {}
  void clear() { len = val = le = ri = 0; }
} a[N * 4];
void build(int k, int l, int r) {
  a[k].clear();
  a[k].len = r - l + 1;
  if (l == r) return;
  int mid = l + r >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
}
inline info merge(const info &a, const info &b) {
  info res;
  res.len = a.len + b.len;
  res.val = a.val + b.val;
  if (a.ri && b.le) {
    res.val -= F[a.ri] + F[b.le];
    res.val += F[a.ri + b.le];
  }
  res.le = a.le;
  if (a.le == a.len) res.le += b.le;
  res.ri = b.ri;
  if (b.ri == b.len) res.ri += a.ri;
  return res;
}
void modify(int k, int l, int r, int p) {
  if (l == r) {
    a[k].le = a[k].ri = 1;
    a[k].val = F[1];
    return;
  }
  int mid = l + r >> 1;
  if (p <= mid)
    modify(k << 1, l, mid, p);
  else
    modify(k << 1 | 1, mid + 1, r, p);
  a[k] = merge(a[k << 1], a[k << 1 | 1]);
}
info Query(int k, int l, int r, int p, int q) {
  if (l >= p && r <= q) return a[k];
  int mid = l + r >> 1;
  if (mid >= q) return Query(k << 1, l, mid, p, q);
  if (mid + 1 <= p) return Query(k << 1 | 1, mid + 1, r, p, q);
  return merge(Query(k << 1, l, mid, p, q),
               Query(k << 1 | 1, mid + 1, r, p, q));
}
info work(int x, int y) {
  info a, b;
  a.clear();
  b.clear();
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]]) {
      a = merge(Query(1, 1, n, mark[top[x]], mark[x]), a);
      x = fa[top[x]];
    } else {
      b = merge(Query(1, 1, n, mark[top[y]], mark[y]), b);
      y = fa[top[y]];
    }
  }
  if (dep[x] > dep[y]) {
    a = merge(Query(1, 1, n, mark[y] + 1, mark[x]), a);
  }
  if (dep[y] > dep[x]) {
    b = merge(Query(1, 1, n, mark[x] + 1, mark[y]), b);
  }
  swap(a.le, a.ri);
  return merge(a, b);
}
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++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    G[u].push_back(v);
    G[v].push_back(u);
    W[u].push_back(w);
    W[v].push_back(w);
  }
  fw[1] = -2e9;
  for (int i = 1; i <= q; i++) {
    Q[i].input();
    Q[i].id = i;
  }
  sort(Q + 1, Q + 1 + q);
  dfs1(1, 0);
  top[1] = 1;
  tot = 1;
  mark[1] = 1;
  dfs2(1, 0);
  build(1, 1, n);
  int p = 1;
  sort(id + 1, id + 1 + n, cmp);
  for (int i = 1; i <= q; i++) {
    while (p < n && fw[id[p]] >= Q[i].l) {
      modify(1, 1, n, mark[id[p]]);
      p++;
    }
    info res = work(Q[i].u, Q[i].v);
    ans[Q[i].id] = res.val;
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}

```