#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
const int M = 20 * N;
int fib[N];
int L[M], R[M], cnt;
struct A {
  int sum, val, lef, rig;
  A() : sum(0), val(0), lef(0), rig(0) {}
} data[M];
A operator+(const A& x, const A& y) {
  A z;
  z.sum = x.sum + y.sum;
  z.val = x.val + y.val - fib[x.rig] - fib[y.lef] + fib[x.rig + y.lef];
  z.lef = x.lef == x.sum ? x.sum + y.lef : x.lef;
  z.rig = y.rig == y.sum ? x.rig + y.sum : y.rig;
  return z;
}
void init_(int& k, int l, int r) {
  k = ++cnt;
  if (l == r - 1) {
    data[k].sum = 1;
    return;
  }
  init_(L[k], l, ((l + r) >> 1));
  init_(R[k], ((l + r) >> 1), r);
  data[k] = data[L[k]] + data[R[k]];
}
int modify(int k, int l, int r, int t) {
  int x = ++cnt;
  if (l == r - 1) {
    data[x].sum = 1;
    data[x].val = fib[1];
    data[x].lef = 1;
    data[x].rig = 1;
    return x;
  }
  L[x] = L[k];
  R[x] = R[k];
  if (t < ((l + r) >> 1))
    L[x] = modify(L[k], l, ((l + r) >> 1), t);
  else
    R[x] = modify(R[k], ((l + r) >> 1), r, t);
  data[x] = data[L[x]] + data[R[x]];
  return x;
}
A query(int k, int l, int r, int t, int v) {
  if (v <= l || r <= t) return data[0];
  if (t <= l && r <= v) return data[k];
  A x = query(L[k], l, ((l + r) >> 1), t, v);
  A y = query(R[k], ((l + r) >> 1), r, t, v);
  return x + y;
}
vector<int> ch[N];
int fa[N], dep[N], son[N], size[N];
void init_(int u, int f) {
  fa[u] = f;
  dep[u] = dep[f] + 1;
  size[u] = 1;
  for (int i = 0; i <= (int)ch[u].size() - 1; i++) {
    int v = ch[u][i];
    if (v != f) {
      init_(v, u);
      size[u] += size[v];
      if (size[v] > size[son[u]]) son[u] = v;
    }
  }
}
int top[N], idx[N], tot;
void Build(int u, int f, int tp) {
  top[u] = tp;
  idx[u] = ++tot;
  if (son[u]) Build(son[u], u, tp);
  for (int i = 0; i <= (int)ch[u].size() - 1; i++) {
    int v = ch[u][i];
    if (v != f && v != son[u]) Build(v, u, v);
  }
}
A query(int u, int v, int r) {
  A x = data[0];
  A y = data[0];
  int tag = 0;
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v), swap(x, y), tag ^= 1;
    A res = query(r, 1, tot + 1, idx[top[u]], idx[u] + 1);
    x = res + x;
    u = fa[top[u]];
  }
  if (dep[u] < dep[v]) swap(u, v), swap(x, y), tag ^= 1;
  A res = query(r, 1, tot + 1, idx[v] + 1, idx[u] + 1);
  x = res + x;
  if (tag) swap(u, v), swap(x, y), tag ^= 1;
  swap(x.lef, x.rig);
  return x + y;
}
int root[N];
int x[N], y[N], z[N], _[N];
bool cmp(int a, int b) { return z[a] > z[b]; }
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n - 1; i++) scanf("%d", fib + i);
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d%d%d", x + i, y + i, z + i);
    ch[x[i]].push_back(y[i]);
    ch[y[i]].push_back(x[i]);
  }
  init_(1, 0);
  Build(1, 0, 1);
  init_(root[0], 1, n + 1);
  for (int i = 1; i <= n - 1; i++) _[i] = i;
  sort(_ + 1, _ + n, cmp);
  for (int j = 1; j <= n - 1; j++) {
    int i = _[j];
    if (fa[y[i]] == x[i]) swap(x[i], y[i]);
    root[j] = modify(root[j - 1], 1, n + 1, idx[x[i]]);
  }
  sort(z + 1, z + n, greater<int>());
  while (m--) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    int i = upper_bound(z + 1, z + n, w, greater<int>()) - z - 1;
    A ans = query(u, v, root[i]);
    printf("%d\n", ans.val);
  }
  return 0;
}

### Prompt

Please formulate 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 N = 100100;
const int M = 20 * N;
int fib[N];
int L[M], R[M], cnt;
struct A {
  int sum, val, lef, rig;
  A() : sum(0), val(0), lef(0), rig(0) {}
} data[M];
A operator+(const A& x, const A& y) {
  A z;
  z.sum = x.sum + y.sum;
  z.val = x.val + y.val - fib[x.rig] - fib[y.lef] + fib[x.rig + y.lef];
  z.lef = x.lef == x.sum ? x.sum + y.lef : x.lef;
  z.rig = y.rig == y.sum ? x.rig + y.sum : y.rig;
  return z;
}
void init_(int& k, int l, int r) {
  k = ++cnt;
  if (l == r - 1) {
    data[k].sum = 1;
    return;
  }
  init_(L[k], l, ((l + r) >> 1));
  init_(R[k], ((l + r) >> 1), r);
  data[k] = data[L[k]] + data[R[k]];
}
int modify(int k, int l, int r, int t) {
  int x = ++cnt;
  if (l == r - 1) {
    data[x].sum = 1;
    data[x].val = fib[1];
    data[x].lef = 1;
    data[x].rig = 1;
    return x;
  }
  L[x] = L[k];
  R[x] = R[k];
  if (t < ((l + r) >> 1))
    L[x] = modify(L[k], l, ((l + r) >> 1), t);
  else
    R[x] = modify(R[k], ((l + r) >> 1), r, t);
  data[x] = data[L[x]] + data[R[x]];
  return x;
}
A query(int k, int l, int r, int t, int v) {
  if (v <= l || r <= t) return data[0];
  if (t <= l && r <= v) return data[k];
  A x = query(L[k], l, ((l + r) >> 1), t, v);
  A y = query(R[k], ((l + r) >> 1), r, t, v);
  return x + y;
}
vector<int> ch[N];
int fa[N], dep[N], son[N], size[N];
void init_(int u, int f) {
  fa[u] = f;
  dep[u] = dep[f] + 1;
  size[u] = 1;
  for (int i = 0; i <= (int)ch[u].size() - 1; i++) {
    int v = ch[u][i];
    if (v != f) {
      init_(v, u);
      size[u] += size[v];
      if (size[v] > size[son[u]]) son[u] = v;
    }
  }
}
int top[N], idx[N], tot;
void Build(int u, int f, int tp) {
  top[u] = tp;
  idx[u] = ++tot;
  if (son[u]) Build(son[u], u, tp);
  for (int i = 0; i <= (int)ch[u].size() - 1; i++) {
    int v = ch[u][i];
    if (v != f && v != son[u]) Build(v, u, v);
  }
}
A query(int u, int v, int r) {
  A x = data[0];
  A y = data[0];
  int tag = 0;
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v), swap(x, y), tag ^= 1;
    A res = query(r, 1, tot + 1, idx[top[u]], idx[u] + 1);
    x = res + x;
    u = fa[top[u]];
  }
  if (dep[u] < dep[v]) swap(u, v), swap(x, y), tag ^= 1;
  A res = query(r, 1, tot + 1, idx[v] + 1, idx[u] + 1);
  x = res + x;
  if (tag) swap(u, v), swap(x, y), tag ^= 1;
  swap(x.lef, x.rig);
  return x + y;
}
int root[N];
int x[N], y[N], z[N], _[N];
bool cmp(int a, int b) { return z[a] > z[b]; }
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n - 1; i++) scanf("%d", fib + i);
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d%d%d", x + i, y + i, z + i);
    ch[x[i]].push_back(y[i]);
    ch[y[i]].push_back(x[i]);
  }
  init_(1, 0);
  Build(1, 0, 1);
  init_(root[0], 1, n + 1);
  for (int i = 1; i <= n - 1; i++) _[i] = i;
  sort(_ + 1, _ + n, cmp);
  for (int j = 1; j <= n - 1; j++) {
    int i = _[j];
    if (fa[y[i]] == x[i]) swap(x[i], y[i]);
    root[j] = modify(root[j - 1], 1, n + 1, idx[x[i]]);
  }
  sort(z + 1, z + n, greater<int>());
  while (m--) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    int i = upper_bound(z + 1, z + n, w, greater<int>()) - z - 1;
    A ans = query(u, v, root[i]);
    printf("%d\n", ans.val);
  }
  return 0;
}

```