#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int off = 1 << 17;
int F[maxn];
struct Edge {
  int to, w;
};
vector<Edge> adj[maxn];
struct Query {
  int a, b, w, i;
} q[maxn];
bool operator<(const Query &a, const Query &b) { return a.w > b.w; }
int srt[maxn];
int ans[maxn];
int length[maxn];
int parent[maxn];
int depth[maxn];
int size[maxn];
int chain[maxn];
int home[maxn];
void dfs(int x, int from) {
  size[x] = 1;
  parent[x] = from;
  for (Edge e : adj[x]) {
    if (e.to == from) continue;
    length[e.to] = e.w;
    depth[e.to] = depth[x] + 1;
    dfs(e.to, x);
    size[x] += size[e.to];
  }
}
void build_heavy(int x, int from, int c, int h) {
  chain[x] = c;
  home[x] = h++;
  int mx = -1;
  for (Edge e : adj[x]) {
    if (e.to == from) continue;
    if (mx == -1 | size[e.to] > size[mx]) mx = e.to;
  }
  if (mx == -1) return;
  build_heavy(mx, x, c, h);
  h += size[mx];
  for (Edge e : adj[x]) {
    if (e.to == from || e.to == mx) continue;
    build_heavy(e.to, x, e.to, h);
    h += size[e.to];
  }
}
int lca(int a, int b) {
  while (chain[a] != chain[b]) {
    if (depth[chain[a]] < depth[chain[b]]) swap(a, b);
    a = parent[chain[a]];
  }
  return depth[a] < depth[b] ? a : b;
}
struct Node {
  int l, r, w, sum;
} tree[2 * off];
inline Node reverse(const Node &a) { return {a.r, a.l, a.w, a.sum}; }
Node operator+(const Node &a, const Node &b) {
  int l = a.l + (a.l == a.w) * b.l;
  int r = b.r + (b.r == b.w) * a.r;
  int w = a.w + b.w;
  int sum = a.sum + b.sum + (l < a.w && r < b.w) * F[a.r + b.l];
  return {l, r, w, sum};
}
void update(int x) {
  x += off;
  tree[x] = {1, 1, 1, 0};
  for (x /= 2; x > 0; x /= 2) tree[x] = tree[2 * x] + tree[2 * x + 1];
}
Node query(int lo, int hi, int a = 0, int b = off, int x = 1) {
  if (a >= hi || b <= lo) return {0, 0, 0, 0};
  if (a >= lo && b <= hi) return tree[x];
  return query(lo, hi, a, (a + b) / 2, 2 * x) +
         query(lo, hi, (a + b) / 2, b, 2 * x + 1);
}
Node path(int a, int b) {
  Node ret = {0, 0, 0, 0};
  while (chain[a] != chain[b]) {
    ret = query(home[chain[a]], home[a] + 1) + ret;
    a = parent[chain[a]];
  }
  return query(home[b] + 1, home[a] + 1) + ret;
}
int main() {
  int N, Q;
  scanf("%d%d", &N, &Q);
  for (int _n(N), i(1); i < _n; i++) scanf("%d", F + i);
  for (int _n(N - 1), i(0); i < _n; i++) {
    int a, b, w;
    scanf("%d%d%d", &a, &b, &w);
    --a, --b;
    adj[a].push_back({b, w});
    adj[b].push_back({a, w});
  }
  for (int _n(Q), i(0); i < _n; i++) q[i].i = i;
  for (int _n(Q), i(0); i < _n; i++)
    scanf("%d%d%d", &q[i].a, &q[i].b, &q[i].w), --q[i].a, --q[i].b;
  sort(q, q + Q);
  length[0] = -1e9;
  dfs(0, -1);
  build_heavy(0, -1, 0, 0);
  for (int _n(2 * off), x(off); x < _n; x++) tree[x].w = 1;
  for (int x = off - 1; x > 0; --x) tree[x] = tree[2 * x] + tree[2 * x + 1];
  for (int _n(N), i(0); i < _n; i++) srt[i] = i;
  sort(srt, srt + N, [](int a, int b) { return length[a] > length[b]; });
  int pos = 0;
  for (int _n(Q), i(0); i < _n; i++) {
    for (; pos < N && length[srt[pos]] >= q[i].w; ++pos) update(home[srt[pos]]);
    int a = q[i].a;
    int b = q[i].b;
    int c = lca(a, b);
    Node A = path(a, c);
    Node B = path(b, c);
    Node C = reverse(A) + B;
    ans[q[i].i] = C.sum + F[C.l] + (C.l < C.w) * F[C.r];
  }
  for (int _n(Q), i(0); i < _n; i++) printf("%d\n", ans[i]);
  return 0;
}

### Prompt

Your challenge is to write 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 maxn = 1e5 + 5;
const int off = 1 << 17;
int F[maxn];
struct Edge {
  int to, w;
};
vector<Edge> adj[maxn];
struct Query {
  int a, b, w, i;
} q[maxn];
bool operator<(const Query &a, const Query &b) { return a.w > b.w; }
int srt[maxn];
int ans[maxn];
int length[maxn];
int parent[maxn];
int depth[maxn];
int size[maxn];
int chain[maxn];
int home[maxn];
void dfs(int x, int from) {
  size[x] = 1;
  parent[x] = from;
  for (Edge e : adj[x]) {
    if (e.to == from) continue;
    length[e.to] = e.w;
    depth[e.to] = depth[x] + 1;
    dfs(e.to, x);
    size[x] += size[e.to];
  }
}
void build_heavy(int x, int from, int c, int h) {
  chain[x] = c;
  home[x] = h++;
  int mx = -1;
  for (Edge e : adj[x]) {
    if (e.to == from) continue;
    if (mx == -1 | size[e.to] > size[mx]) mx = e.to;
  }
  if (mx == -1) return;
  build_heavy(mx, x, c, h);
  h += size[mx];
  for (Edge e : adj[x]) {
    if (e.to == from || e.to == mx) continue;
    build_heavy(e.to, x, e.to, h);
    h += size[e.to];
  }
}
int lca(int a, int b) {
  while (chain[a] != chain[b]) {
    if (depth[chain[a]] < depth[chain[b]]) swap(a, b);
    a = parent[chain[a]];
  }
  return depth[a] < depth[b] ? a : b;
}
struct Node {
  int l, r, w, sum;
} tree[2 * off];
inline Node reverse(const Node &a) { return {a.r, a.l, a.w, a.sum}; }
Node operator+(const Node &a, const Node &b) {
  int l = a.l + (a.l == a.w) * b.l;
  int r = b.r + (b.r == b.w) * a.r;
  int w = a.w + b.w;
  int sum = a.sum + b.sum + (l < a.w && r < b.w) * F[a.r + b.l];
  return {l, r, w, sum};
}
void update(int x) {
  x += off;
  tree[x] = {1, 1, 1, 0};
  for (x /= 2; x > 0; x /= 2) tree[x] = tree[2 * x] + tree[2 * x + 1];
}
Node query(int lo, int hi, int a = 0, int b = off, int x = 1) {
  if (a >= hi || b <= lo) return {0, 0, 0, 0};
  if (a >= lo && b <= hi) return tree[x];
  return query(lo, hi, a, (a + b) / 2, 2 * x) +
         query(lo, hi, (a + b) / 2, b, 2 * x + 1);
}
Node path(int a, int b) {
  Node ret = {0, 0, 0, 0};
  while (chain[a] != chain[b]) {
    ret = query(home[chain[a]], home[a] + 1) + ret;
    a = parent[chain[a]];
  }
  return query(home[b] + 1, home[a] + 1) + ret;
}
int main() {
  int N, Q;
  scanf("%d%d", &N, &Q);
  for (int _n(N), i(1); i < _n; i++) scanf("%d", F + i);
  for (int _n(N - 1), i(0); i < _n; i++) {
    int a, b, w;
    scanf("%d%d%d", &a, &b, &w);
    --a, --b;
    adj[a].push_back({b, w});
    adj[b].push_back({a, w});
  }
  for (int _n(Q), i(0); i < _n; i++) q[i].i = i;
  for (int _n(Q), i(0); i < _n; i++)
    scanf("%d%d%d", &q[i].a, &q[i].b, &q[i].w), --q[i].a, --q[i].b;
  sort(q, q + Q);
  length[0] = -1e9;
  dfs(0, -1);
  build_heavy(0, -1, 0, 0);
  for (int _n(2 * off), x(off); x < _n; x++) tree[x].w = 1;
  for (int x = off - 1; x > 0; --x) tree[x] = tree[2 * x] + tree[2 * x + 1];
  for (int _n(N), i(0); i < _n; i++) srt[i] = i;
  sort(srt, srt + N, [](int a, int b) { return length[a] > length[b]; });
  int pos = 0;
  for (int _n(Q), i(0); i < _n; i++) {
    for (; pos < N && length[srt[pos]] >= q[i].w; ++pos) update(home[srt[pos]]);
    int a = q[i].a;
    int b = q[i].b;
    int c = lca(a, b);
    Node A = path(a, c);
    Node B = path(b, c);
    Node C = reverse(A) + B;
    ans[q[i].i] = C.sum + F[C.l] + (C.l < C.w) * F[C.r];
  }
  for (int _n(Q), i(0); i < _n; i++) printf("%d\n", ans[i]);
  return 0;
}

```