#include <bits/stdc++.h>
using namespace std;
const int Maxn = 2e5 + 100;
int n, m, tmp, cnt, f[Maxn], ans[Maxn], now[Maxn], to[Maxn], nxt[Maxn],
    len[Maxn];
struct Q {
  int u, v, l, id;
  friend bool operator<(Q a, Q b) { return a.l < b.l; }
} q[Maxn];
struct quaternion {
  int l, r, ans, sum;
  quaternion(int l = 0, int r = 0, int ans = 0, int sum = 1)
      : l(l), r(r), ans(ans), sum(sum) {}
  friend quaternion operator+(quaternion a, quaternion b) {
    quaternion c(a.l, b.r, a.ans + b.ans - f[a.r] - f[b.l] + f[a.r + b.l],
                 a.sum + b.sum);
    if (a.l == a.sum) c.l += b.l;
    if (b.l == b.sum) c.r += a.r;
    return c;
  }
};
struct node {
  node *ch[2], *f;
  quaternion v, s;
} t[Maxn], *nil = t;
pair<int, node*> s[Maxn];
void add(int u, int v, int l) {
  to[++tmp] = v, nxt[tmp] = now[u], len[tmp] = l, now[u] = tmp;
  to[++tmp] = u, nxt[tmp] = now[v], len[tmp] = l, now[v] = tmp;
}
bool root(node* x) {
  return x == nil || (!(x->f->ch[0] == x || x->f->ch[1] == x));
}
void maintain(node* x) { x->s = x->ch[0]->s + x->v + x->ch[1]->s; }
void dfs(int x, int f) {
  for (int i = now[x]; i; i = nxt[i])
    if (to[i] != f) {
      s[++cnt] = make_pair(len[i], t + to[i]);
      (t + to[i])->f = t + x;
      dfs(to[i], x);
    }
}
void rotate(node* x) {
  node *y = x->f, *z = y->f;
  bool k = y->ch[1] == x;
  (y->ch[k] = x->ch[k ^ 1])->f = y;
  (x->ch[k ^ 1] = y)->f = x;
  if (z->ch[0] == y || z->ch[1] == y) z->ch[z->ch[1] == y] = x;
  x->f = z;
  maintain(y);
  maintain(x);
}
void splay(node* x) {
  for (node* y; !root(x); rotate(x))
    if (!root(y = x->f))
      rotate((x->f->ch[0] == x) == (y->f->ch[0] == y) ? y : x);
}
node* access(node* x) {
  node* y;
  for (y = nil; x != nil; y = x, x = x->f) {
    splay(x);
    x->ch[1] = y;
    maintain(x);
  }
  return y;
}
void modify(node* x) {
  access(x);
  splay(x);
  x->v = quaternion(1, 1, f[1], 1);
  maintain(x);
}
int query(node* x, node* y) {
  access(x);
  node* lca = access(y);
  quaternion a, b;
  access(x);
  splay(lca);
  a = lca->ch[1]->s;
  access(y);
  splay(lca);
  b = lca->ch[1]->s;
  swap(a.l, a.r);
  return (a + b).ans;
}
int main(int argc, const char* argv[]) {
  ios::sync_with_stdio(0);
  int i;
  cin >> n >> m;
  for (node* x = t + 1; x <= t + n; x++)
    x->ch[0] = x->ch[1] = x->f = nil, x->v = x->s = quaternion();
  nil->v = nil->s = quaternion(0, 0, 0, 0);
  for (i = 1; i < n; i++) cin >> f[i];
  for (i = 1; i < n; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    add(x, y, z);
  }
  dfs(1, 0);
  sort(s + 1, s + n);
  for (i = 1; i <= m; i++) {
    cin >> q[i].u >> q[i].v >> q[i].l;
    q[i].id = i;
  }
  sort(q + 1, q + m + 1);
  int p = n - 1;
  for (i = m; i >= 1; i--) {
    for (; p && q[i].l <= s[p].first; modify(s[p].second), p--)
      ;
    ans[q[i].id] = query(t + q[i].u, t + q[i].v);
  }
  for (i = 1; i <= m; i++) cout << ans[i] << endl;
  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;
const int Maxn = 2e5 + 100;
int n, m, tmp, cnt, f[Maxn], ans[Maxn], now[Maxn], to[Maxn], nxt[Maxn],
    len[Maxn];
struct Q {
  int u, v, l, id;
  friend bool operator<(Q a, Q b) { return a.l < b.l; }
} q[Maxn];
struct quaternion {
  int l, r, ans, sum;
  quaternion(int l = 0, int r = 0, int ans = 0, int sum = 1)
      : l(l), r(r), ans(ans), sum(sum) {}
  friend quaternion operator+(quaternion a, quaternion b) {
    quaternion c(a.l, b.r, a.ans + b.ans - f[a.r] - f[b.l] + f[a.r + b.l],
                 a.sum + b.sum);
    if (a.l == a.sum) c.l += b.l;
    if (b.l == b.sum) c.r += a.r;
    return c;
  }
};
struct node {
  node *ch[2], *f;
  quaternion v, s;
} t[Maxn], *nil = t;
pair<int, node*> s[Maxn];
void add(int u, int v, int l) {
  to[++tmp] = v, nxt[tmp] = now[u], len[tmp] = l, now[u] = tmp;
  to[++tmp] = u, nxt[tmp] = now[v], len[tmp] = l, now[v] = tmp;
}
bool root(node* x) {
  return x == nil || (!(x->f->ch[0] == x || x->f->ch[1] == x));
}
void maintain(node* x) { x->s = x->ch[0]->s + x->v + x->ch[1]->s; }
void dfs(int x, int f) {
  for (int i = now[x]; i; i = nxt[i])
    if (to[i] != f) {
      s[++cnt] = make_pair(len[i], t + to[i]);
      (t + to[i])->f = t + x;
      dfs(to[i], x);
    }
}
void rotate(node* x) {
  node *y = x->f, *z = y->f;
  bool k = y->ch[1] == x;
  (y->ch[k] = x->ch[k ^ 1])->f = y;
  (x->ch[k ^ 1] = y)->f = x;
  if (z->ch[0] == y || z->ch[1] == y) z->ch[z->ch[1] == y] = x;
  x->f = z;
  maintain(y);
  maintain(x);
}
void splay(node* x) {
  for (node* y; !root(x); rotate(x))
    if (!root(y = x->f))
      rotate((x->f->ch[0] == x) == (y->f->ch[0] == y) ? y : x);
}
node* access(node* x) {
  node* y;
  for (y = nil; x != nil; y = x, x = x->f) {
    splay(x);
    x->ch[1] = y;
    maintain(x);
  }
  return y;
}
void modify(node* x) {
  access(x);
  splay(x);
  x->v = quaternion(1, 1, f[1], 1);
  maintain(x);
}
int query(node* x, node* y) {
  access(x);
  node* lca = access(y);
  quaternion a, b;
  access(x);
  splay(lca);
  a = lca->ch[1]->s;
  access(y);
  splay(lca);
  b = lca->ch[1]->s;
  swap(a.l, a.r);
  return (a + b).ans;
}
int main(int argc, const char* argv[]) {
  ios::sync_with_stdio(0);
  int i;
  cin >> n >> m;
  for (node* x = t + 1; x <= t + n; x++)
    x->ch[0] = x->ch[1] = x->f = nil, x->v = x->s = quaternion();
  nil->v = nil->s = quaternion(0, 0, 0, 0);
  for (i = 1; i < n; i++) cin >> f[i];
  for (i = 1; i < n; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    add(x, y, z);
  }
  dfs(1, 0);
  sort(s + 1, s + n);
  for (i = 1; i <= m; i++) {
    cin >> q[i].u >> q[i].v >> q[i].l;
    q[i].id = i;
  }
  sort(q + 1, q + m + 1);
  int p = n - 1;
  for (i = m; i >= 1; i--) {
    for (; p && q[i].l <= s[p].first; modify(s[p].second), p--)
      ;
    ans[q[i].id] = query(t + q[i].u, t + q[i].v);
  }
  for (i = 1; i <= m; i++) cout << ans[i] << endl;
  return 0;
}

```