#include <bits/stdc++.h>
using namespace std;
struct Node {
  int val, al, bound[2];
  void init() { val = al = bound[0] = bound[1] = 0; }
  void reverse() { swap(bound[0], bound[1]); }
} node[101000 << 2];
struct Proc {
  int a, b, c, p;
  void read() { scanf("%d %d %d", &a, &b, &c); }
} proc[101000], Edge[101000];
bool cmp(const Proc &a, const Proc &b) { return (a.c < b.c); }
struct str {
  int v, nex;
} edge[101000 << 1];
int f[101000], fst[101000], fa[101000], dep[101000], mark[101000];
int ans[101000], size[101000], son[101000], anc[101000];
int n, m, e, top;
void make_edge(int a, int b) {
  edge[++e].nex = fst[a];
  fst[a] = e;
  edge[e].v = b;
  edge[++e].nex = fst[b];
  fst[b] = e;
  edge[e].v = a;
}
void dfs(int u) {
  size[u] = 1;
  dep[u] = dep[fa[u]] + 1;
  for (int i = fst[u]; i; i = edge[i].nex) {
    int v = edge[i].v;
    if (v == fa[u]) continue;
    fa[v] = u;
    dfs(v);
    if (size[v] > size[son[u]]) son[u] = v;
    size[u] += size[v];
  }
  return;
}
Node merge(Node A, Node B) {
  Node ans;
  ans.init();
  if (A.al && B.al) {
    ans.al = 1;
    ans.val = 0;
    ans.bound[0] = ans.bound[1] = A.bound[0] + B.bound[0];
  } else if (B.al) {
    ans.al = 0;
    ans.val = A.val + B.val;
    ans.bound[0] = A.bound[0];
    ans.bound[1] = A.bound[1] + B.bound[1];
  } else if (A.al) {
    ans.al = 0;
    ans.val = A.val + B.val;
    ans.bound[1] = B.bound[1];
    ans.bound[0] = B.bound[0] + A.bound[0];
  } else {
    ans.al = 0;
    ans.val = A.val + B.val + f[A.bound[1] + B.bound[0]];
    ans.bound[0] = A.bound[0];
    ans.bound[1] = B.bound[1];
  }
  return ans;
}
void change(int u, int L, int R, int k) {
  if (L == R) {
    node[u].val = 0;
    node[u].bound[0] = node[u].bound[1] = node[u].al = 1;
    return;
  }
  if (k < (((L + R) >> 1) + 1))
    change((u << 1), L, ((L + R) >> 1), k);
  else
    change((u << 1 | 1), (((L + R) >> 1) + 1), R, k);
  node[u] = merge(node[(u << 1)], node[(u << 1 | 1)]);
}
Node find(int u, int L, int R, int l, int r) {
  if (L == l && R == r) return node[u];
  if (r < (((L + R) >> 1) + 1))
    return find((u << 1), L, ((L + R) >> 1), l, r);
  else if (l > ((L + R) >> 1))
    return find((u << 1 | 1), (((L + R) >> 1) + 1), R, l, r);
  else
    return merge(
        find((u << 1), L, ((L + R) >> 1), l, ((L + R) >> 1)),
        find((u << 1 | 1), (((L + R) >> 1) + 1), R, (((L + R) >> 1) + 1), r));
}
int query(int a, int b) {
  Node A, B;
  A.init();
  B.init();
  while (a != b) {
    if (dep[a] < dep[b]) {
      swap(a, b);
      swap(A, B);
    }
    if (anc[a] == anc[b]) {
      A = merge(find(1, 1, n, mark[son[b]], mark[a]), A);
      break;
    } else {
      if (dep[anc[a]] < dep[anc[b]]) {
        swap(a, b);
        swap(A, B);
      }
      A = merge(find(1, 1, n, mark[anc[a]], mark[a]), A);
      a = fa[anc[a]];
    }
  }
  A.reverse();
  A = merge(A, B);
  return A.val + f[A.bound[0]] + f[A.bound[1]];
}
void solve() {
  int q = n - 1;
  for (int t = m; t; t--) {
    for (; q && Edge[q].c >= proc[t].c; q--)
      change(1, 1, n,
             mark[dep[Edge[q].a] > dep[Edge[q].b] ? Edge[q].a : Edge[q].b]);
    ans[proc[t].p] = query(proc[t].a, proc[t].b);
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i < n; i++) scanf("%d", &f[i]);
  for (int i = 1; i < n; i++) {
    Edge[i].read();
    Edge[i].p = i;
    make_edge(Edge[i].a, Edge[i].b);
  }
  dfs(1);
  for (int u = 1; u <= n; u++) {
    if (son[fa[u]] == u) continue;
    for (int v = u; v; v = son[v]) {
      anc[v] = u;
      mark[v] = ++top;
    }
  }
  sort(Edge + 1, Edge + n, cmp);
  for (int i = 1; i <= m; i++) {
    proc[i].read();
    proc[i].p = i;
  }
  sort(proc + 1, proc + m + 1, cmp);
  solve();
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}

### Prompt

Generate 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;
struct Node {
  int val, al, bound[2];
  void init() { val = al = bound[0] = bound[1] = 0; }
  void reverse() { swap(bound[0], bound[1]); }
} node[101000 << 2];
struct Proc {
  int a, b, c, p;
  void read() { scanf("%d %d %d", &a, &b, &c); }
} proc[101000], Edge[101000];
bool cmp(const Proc &a, const Proc &b) { return (a.c < b.c); }
struct str {
  int v, nex;
} edge[101000 << 1];
int f[101000], fst[101000], fa[101000], dep[101000], mark[101000];
int ans[101000], size[101000], son[101000], anc[101000];
int n, m, e, top;
void make_edge(int a, int b) {
  edge[++e].nex = fst[a];
  fst[a] = e;
  edge[e].v = b;
  edge[++e].nex = fst[b];
  fst[b] = e;
  edge[e].v = a;
}
void dfs(int u) {
  size[u] = 1;
  dep[u] = dep[fa[u]] + 1;
  for (int i = fst[u]; i; i = edge[i].nex) {
    int v = edge[i].v;
    if (v == fa[u]) continue;
    fa[v] = u;
    dfs(v);
    if (size[v] > size[son[u]]) son[u] = v;
    size[u] += size[v];
  }
  return;
}
Node merge(Node A, Node B) {
  Node ans;
  ans.init();
  if (A.al && B.al) {
    ans.al = 1;
    ans.val = 0;
    ans.bound[0] = ans.bound[1] = A.bound[0] + B.bound[0];
  } else if (B.al) {
    ans.al = 0;
    ans.val = A.val + B.val;
    ans.bound[0] = A.bound[0];
    ans.bound[1] = A.bound[1] + B.bound[1];
  } else if (A.al) {
    ans.al = 0;
    ans.val = A.val + B.val;
    ans.bound[1] = B.bound[1];
    ans.bound[0] = B.bound[0] + A.bound[0];
  } else {
    ans.al = 0;
    ans.val = A.val + B.val + f[A.bound[1] + B.bound[0]];
    ans.bound[0] = A.bound[0];
    ans.bound[1] = B.bound[1];
  }
  return ans;
}
void change(int u, int L, int R, int k) {
  if (L == R) {
    node[u].val = 0;
    node[u].bound[0] = node[u].bound[1] = node[u].al = 1;
    return;
  }
  if (k < (((L + R) >> 1) + 1))
    change((u << 1), L, ((L + R) >> 1), k);
  else
    change((u << 1 | 1), (((L + R) >> 1) + 1), R, k);
  node[u] = merge(node[(u << 1)], node[(u << 1 | 1)]);
}
Node find(int u, int L, int R, int l, int r) {
  if (L == l && R == r) return node[u];
  if (r < (((L + R) >> 1) + 1))
    return find((u << 1), L, ((L + R) >> 1), l, r);
  else if (l > ((L + R) >> 1))
    return find((u << 1 | 1), (((L + R) >> 1) + 1), R, l, r);
  else
    return merge(
        find((u << 1), L, ((L + R) >> 1), l, ((L + R) >> 1)),
        find((u << 1 | 1), (((L + R) >> 1) + 1), R, (((L + R) >> 1) + 1), r));
}
int query(int a, int b) {
  Node A, B;
  A.init();
  B.init();
  while (a != b) {
    if (dep[a] < dep[b]) {
      swap(a, b);
      swap(A, B);
    }
    if (anc[a] == anc[b]) {
      A = merge(find(1, 1, n, mark[son[b]], mark[a]), A);
      break;
    } else {
      if (dep[anc[a]] < dep[anc[b]]) {
        swap(a, b);
        swap(A, B);
      }
      A = merge(find(1, 1, n, mark[anc[a]], mark[a]), A);
      a = fa[anc[a]];
    }
  }
  A.reverse();
  A = merge(A, B);
  return A.val + f[A.bound[0]] + f[A.bound[1]];
}
void solve() {
  int q = n - 1;
  for (int t = m; t; t--) {
    for (; q && Edge[q].c >= proc[t].c; q--)
      change(1, 1, n,
             mark[dep[Edge[q].a] > dep[Edge[q].b] ? Edge[q].a : Edge[q].b]);
    ans[proc[t].p] = query(proc[t].a, proc[t].b);
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i < n; i++) scanf("%d", &f[i]);
  for (int i = 1; i < n; i++) {
    Edge[i].read();
    Edge[i].p = i;
    make_edge(Edge[i].a, Edge[i].b);
  }
  dfs(1);
  for (int u = 1; u <= n; u++) {
    if (son[fa[u]] == u) continue;
    for (int v = u; v; v = son[v]) {
      anc[v] = u;
      mark[v] = ++top;
    }
  }
  sort(Edge + 1, Edge + n, cmp);
  for (int i = 1; i <= m; i++) {
    proc[i].read();
    proc[i].p = i;
  }
  sort(proc + 1, proc + m + 1, cmp);
  solve();
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}

```