#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Edge {
  int u, v, w;
  bool operator<(const Edge &a) const { return w < a.w; }
} e[N];
vector<int> G[N];
int F[N];
struct Query {
  int u, v, w, id;
  bool operator<(const Query &a) const { return w < a.w; }
} qy[N];
int dep[N], sz[N], son[N], fa[N][20];
int tid[N], top[N], label = 0;
void dfs1(int u, int father, int depth) {
  fa[u][0] = father;
  dep[u] = depth;
  son[u] = 0;
  sz[u] = 1;
  int maxsize = 0;
  for (int i = 1; i < 20; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (int i = 0; i < (int)G[u].size(); ++i) {
    int v = G[u][i];
    if (v == father) continue;
    dfs1(v, u, depth + 1);
    sz[u] += sz[v];
    if (sz[v] > maxsize) {
      maxsize = sz[v];
      son[u] = v;
    }
  }
}
void dfs2(int u, int ancestor) {
  tid[u] = ++label;
  top[u] = ancestor;
  if (son[u]) dfs2(son[u], ancestor);
  for (int i = 0; i < (int)G[u].size(); ++i) {
    int v = G[u][i];
    if (v == son[u] || v == fa[u][0]) continue;
    dfs2(v, v);
  }
}
inline int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 19; i >= 0; --i) {
    if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
  }
  if (u == v) return u;
  for (int i = 19; i >= 0; --i)
    if (fa[u][i] ^ fa[v][i]) {
      u = fa[u][i];
      v = fa[v][i];
    }
  return fa[u][0];
}
int L[N * 4], R[N * 4];
struct Seg {
  int lx, rx, val, len;
} tr[N * 4];
void build(int id, int l, int r) {
  L[id] = l;
  R[id] = r;
  tr[id].lx = tr[id].rx = tr[id].val = 0;
  tr[id].len = r - l + 1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build((id << 1), l, mid);
  build((id << 1 | 1), mid + 1, r);
}
inline void push_up(Seg *t, Seg *l, Seg *r) {
  t->lx = l->lx == l->len ? l->len + r->lx : l->lx;
  t->rx = r->rx == r->len ? r->len + l->rx : r->rx;
  t->len = l->len + r->len;
  t->val = l->val + r->val - F[l->rx] - F[r->lx] + F[l->rx + r->lx];
}
void updata(int id, int x) {
  if (L[id] == R[id]) {
    tr[id].lx = tr[id].rx = 1;
    tr[id].val = F[1];
    return;
  }
  int mid = (L[id] + R[id]) >> 1;
  updata(x <= mid ? (id << 1) : (id << 1 | 1), x);
  push_up(tr + id, tr + (id << 1), tr + (id << 1 | 1));
}
Seg query(int id, int l, int r) {
  if (L[id] == l && R[id] == r) return tr[id];
  int mid = (L[id] + R[id]) >> 1;
  if (r <= mid) return query((id << 1), l, r);
  if (l > mid) return query((id << 1 | 1), l, r);
  Seg a = query((id << 1), l, mid), b = query((id << 1 | 1), mid + 1, r), c;
  push_up(&c, &a, &b);
  return c;
}
pair<int, int> Inter[100];
int solve(int u, int v) {
  int LCA = lca(u, v);
  int cc = 0, f = top[u];
  while (f != top[LCA]) {
    Inter[cc++] = make_pair(tid[f], tid[u]);
    u = fa[f][0];
    f = top[u];
  }
  if (u != LCA) Inter[cc++] = make_pair(tid[son[LCA]], tid[u]);
  int half = cc;
  f = top[v];
  while (f != top[LCA]) {
    Inter[cc++] = make_pair(tid[f], tid[v]);
    v = fa[f][0];
    f = top[v];
  }
  if (v != LCA) Inter[cc++] = make_pair(tid[son[LCA]], tid[v]);
  reverse(Inter + half, Inter + cc);
  Seg ans, t1, t2;
  ans.lx = ans.rx = ans.len = ans.val = 0;
  for (int i = 0; i < cc; ++i) {
    t1 = query(1, Inter[i].first, Inter[i].second);
    if (i < half) swap(t1.lx, t1.rx);
    push_up(&t2, &ans, &t1);
    ans = t2;
  }
  return ans.val;
}
int ans[N];
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; ++i) scanf("%d", F + i);
  for (int i = 1; i < n; ++i) {
    scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    G[e[i].u].push_back(e[i].v);
    G[e[i].v].push_back(e[i].u);
  }
  for (int i = 0; i < q; ++i) {
    scanf("%d%d%d", &qy[i].u, &qy[i].v, &qy[i].w);
    qy[i].id = i;
  }
  dfs1(1, 1, 0);
  dfs2(1, 1);
  sort(e + 1, e + n);
  sort(qy, qy + q);
  build(1, 1, n);
  for (int i = q - 1, j = n - 1; i >= 0; --i) {
    for (; j >= 1 && e[j].w >= qy[i].w; --j) {
      int u = dep[e[j].u] > dep[e[j].v] ? e[j].u : e[j].v;
      updata(1, tid[u]);
    }
    ans[qy[i].id] = solve(qy[i].u, qy[i].v);
  }
  for (int i = 0; i < q; ++i) printf("%d\n", ans[i]);
  return 0;
}

### Prompt

Your task is to create 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 = 100005;
struct Edge {
  int u, v, w;
  bool operator<(const Edge &a) const { return w < a.w; }
} e[N];
vector<int> G[N];
int F[N];
struct Query {
  int u, v, w, id;
  bool operator<(const Query &a) const { return w < a.w; }
} qy[N];
int dep[N], sz[N], son[N], fa[N][20];
int tid[N], top[N], label = 0;
void dfs1(int u, int father, int depth) {
  fa[u][0] = father;
  dep[u] = depth;
  son[u] = 0;
  sz[u] = 1;
  int maxsize = 0;
  for (int i = 1; i < 20; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (int i = 0; i < (int)G[u].size(); ++i) {
    int v = G[u][i];
    if (v == father) continue;
    dfs1(v, u, depth + 1);
    sz[u] += sz[v];
    if (sz[v] > maxsize) {
      maxsize = sz[v];
      son[u] = v;
    }
  }
}
void dfs2(int u, int ancestor) {
  tid[u] = ++label;
  top[u] = ancestor;
  if (son[u]) dfs2(son[u], ancestor);
  for (int i = 0; i < (int)G[u].size(); ++i) {
    int v = G[u][i];
    if (v == son[u] || v == fa[u][0]) continue;
    dfs2(v, v);
  }
}
inline int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 19; i >= 0; --i) {
    if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
  }
  if (u == v) return u;
  for (int i = 19; i >= 0; --i)
    if (fa[u][i] ^ fa[v][i]) {
      u = fa[u][i];
      v = fa[v][i];
    }
  return fa[u][0];
}
int L[N * 4], R[N * 4];
struct Seg {
  int lx, rx, val, len;
} tr[N * 4];
void build(int id, int l, int r) {
  L[id] = l;
  R[id] = r;
  tr[id].lx = tr[id].rx = tr[id].val = 0;
  tr[id].len = r - l + 1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build((id << 1), l, mid);
  build((id << 1 | 1), mid + 1, r);
}
inline void push_up(Seg *t, Seg *l, Seg *r) {
  t->lx = l->lx == l->len ? l->len + r->lx : l->lx;
  t->rx = r->rx == r->len ? r->len + l->rx : r->rx;
  t->len = l->len + r->len;
  t->val = l->val + r->val - F[l->rx] - F[r->lx] + F[l->rx + r->lx];
}
void updata(int id, int x) {
  if (L[id] == R[id]) {
    tr[id].lx = tr[id].rx = 1;
    tr[id].val = F[1];
    return;
  }
  int mid = (L[id] + R[id]) >> 1;
  updata(x <= mid ? (id << 1) : (id << 1 | 1), x);
  push_up(tr + id, tr + (id << 1), tr + (id << 1 | 1));
}
Seg query(int id, int l, int r) {
  if (L[id] == l && R[id] == r) return tr[id];
  int mid = (L[id] + R[id]) >> 1;
  if (r <= mid) return query((id << 1), l, r);
  if (l > mid) return query((id << 1 | 1), l, r);
  Seg a = query((id << 1), l, mid), b = query((id << 1 | 1), mid + 1, r), c;
  push_up(&c, &a, &b);
  return c;
}
pair<int, int> Inter[100];
int solve(int u, int v) {
  int LCA = lca(u, v);
  int cc = 0, f = top[u];
  while (f != top[LCA]) {
    Inter[cc++] = make_pair(tid[f], tid[u]);
    u = fa[f][0];
    f = top[u];
  }
  if (u != LCA) Inter[cc++] = make_pair(tid[son[LCA]], tid[u]);
  int half = cc;
  f = top[v];
  while (f != top[LCA]) {
    Inter[cc++] = make_pair(tid[f], tid[v]);
    v = fa[f][0];
    f = top[v];
  }
  if (v != LCA) Inter[cc++] = make_pair(tid[son[LCA]], tid[v]);
  reverse(Inter + half, Inter + cc);
  Seg ans, t1, t2;
  ans.lx = ans.rx = ans.len = ans.val = 0;
  for (int i = 0; i < cc; ++i) {
    t1 = query(1, Inter[i].first, Inter[i].second);
    if (i < half) swap(t1.lx, t1.rx);
    push_up(&t2, &ans, &t1);
    ans = t2;
  }
  return ans.val;
}
int ans[N];
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; ++i) scanf("%d", F + i);
  for (int i = 1; i < n; ++i) {
    scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    G[e[i].u].push_back(e[i].v);
    G[e[i].v].push_back(e[i].u);
  }
  for (int i = 0; i < q; ++i) {
    scanf("%d%d%d", &qy[i].u, &qy[i].v, &qy[i].w);
    qy[i].id = i;
  }
  dfs1(1, 1, 0);
  dfs2(1, 1);
  sort(e + 1, e + n);
  sort(qy, qy + q);
  build(1, 1, n);
  for (int i = q - 1, j = n - 1; i >= 0; --i) {
    for (; j >= 1 && e[j].w >= qy[i].w; --j) {
      int u = dep[e[j].u] > dep[e[j].v] ? e[j].u : e[j].v;
      updata(1, tid[u]);
    }
    ans[qy[i].id] = solve(qy[i].u, qy[i].v);
  }
  for (int i = 0; i < q; ++i) printf("%d\n", ans[i]);
  return 0;
}

```