#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e5 + 10;
struct node {
  long long res, pre, suf, total;
  node() {
    res = 0;
    pre = 0;
    suf = 0;
    total = 0;
  }
};
node segt[4 * MAXN];
vector<pair<long long, long long> > vertex[MAXN];
vector<pair<long long, long long> > query;
long long s[MAXN];
long long e[MAXN];
long long f[MAXN];
long long st[MAXN];
long long ft[MAXN];
long long up[MAXN];
long long par[MAXN];
long long len[MAXN];
long long ans[MAXN];
long long subtree[MAXN];
bool check[MAXN];
node val_0, val_1;
long long n, t = 0;
bool cmp(const pair<long long, long long>& x,
         const pair<long long, long long>& y) {
  return subtree[x.first] > subtree[y.first];
}
bool is_par(const long long& v, const long long& u) {
  return (st[v] <= st[u] && ft[v] >= ft[u]);
}
void set_dfs(long long v) {
  check[v] = true;
  subtree[v] = 1;
  for (long long i = 0; i < vertex[v].size(); i++) {
    if (!check[vertex[v][i].first]) {
      par[vertex[v][i].first] = v;
      query.push_back(make_pair(vertex[v][i].second, vertex[v][i].first));
      set_dfs(vertex[v][i].first);
      subtree[v] += subtree[vertex[v][i].first];
    }
  }
}
void set_time_dfs(long long v, long long u) {
  check[v] = true;
  st[v] = ++t;
  up[v] = u;
  bool flag = false;
  for (long long i = 0; i < vertex[v].size(); i++) {
    if (!check[vertex[v][i].first]) {
      if (!flag) {
        set_time_dfs(vertex[v][i].first, u);
      } else {
        set_time_dfs(vertex[v][i].first, vertex[v][i].first);
      }
      flag = true;
    }
  }
  ft[v] = t;
}
node merge_node(node x, node y) {
  node res;
  res.res = x.res + y.res + f[x.suf + y.pre] - f[x.suf] - f[y.pre];
  res.pre = (x.pre == x.total ? y.pre + x.total : x.pre);
  res.suf = (y.suf == y.total ? x.suf + y.total : y.suf);
  res.total = x.total + y.total;
  return res;
}
void build(long long id, long long L, long long R) {
  if (L == R) {
    segt[id].total = 1;
    return;
  }
  long long mid = (L + R) / 2;
  build(2 * id + 1, L, mid);
  build(2 * id + 2, mid + 1, R);
  segt[id] = merge_node(segt[2 * id + 1], segt[2 * id + 2]);
}
void update(long long id, long long L, long long R, long long p) {
  if (R < L || p < L || p > R) {
    return;
  }
  if (L == R) {
    segt[id].res = f[1];
    segt[id].pre = 1;
    segt[id].suf = 1;
    segt[id].total = 1;
    return;
  }
  long long mid = (L + R) / 2;
  update(2 * id + 1, L, mid, p);
  update(2 * id + 2, mid + 1, R, p);
  segt[id] = merge_node(segt[2 * id + 1], segt[2 * id + 2]);
}
node get_res(long long id, long long L, long long R, long long l, long long r) {
  if (R < L || L > r || R < l) {
    node res;
    return res;
  }
  if (L >= l && R <= r) {
    return segt[id];
  }
  long long mid = (L + R) / 2;
  return merge_node(get_res(2 * id + 1, L, mid, l, r),
                    get_res(2 * id + 2, mid + 1, R, l, r));
}
node solve(long long v, long long u) {
  node res_v, res_u;
  while (!is_par(up[v], u)) {
    node k = get_res(0, 1, n, st[up[v]] + 1, st[v]);
    swap(k.pre, k.suf);
    res_v = merge_node(res_v, k);
    v = up[v];
    if (check[st[v]]) {
      res_v = merge_node(res_v, val_1);
    } else {
      res_v = merge_node(res_v, val_0);
    }
    v = par[v];
  }
  while (!is_par(up[u], v)) {
    res_u = merge_node(get_res(0, 1, n, st[up[u]] + 1, st[u]), res_u);
    u = up[u];
    if (check[st[u]]) {
      res_u = merge_node(val_1, res_u);
    } else {
      res_u = merge_node(val_0, res_u);
    }
    u = par[u];
  }
  if (is_par(u, v)) {
    node k = get_res(0, 1, n, st[u] + 1, st[v]);
    swap(k.pre, k.suf);
    res_u = merge_node(k, res_u);
  } else {
    node k = get_res(0, 1, n, st[v] + 1, st[u]);
    res_v = merge_node(res_v, k);
  }
  return merge_node(res_v, res_u);
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  long long q;
  cin >> n >> q;
  for (long long i = 1; i < n; i++) {
    cin >> f[i];
  }
  for (long long i = 0; i < (n - 1); i++) {
    long long v, u, w;
    cin >> v >> u >> w;
    vertex[v].push_back(make_pair(u, w));
    vertex[u].push_back(make_pair(v, w));
  }
  set_dfs(1);
  for (long long i = 1; i <= n; i++) {
    check[i] = false;
    sort(vertex[i].begin(), vertex[i].end(), cmp);
  }
  par[1] = 1;
  set_time_dfs(1, 1);
  for (long long i = 0; i < q; i++) {
    cin >> s[i] >> e[i] >> len[i];
    query.push_back(make_pair(len[i], -i));
  }
  build(0, 1, n);
  val_1.res = f[1];
  val_1.pre = 1;
  val_1.suf = 1;
  val_1.total = 1;
  val_0.res = 0;
  val_0.pre = 0;
  val_0.suf = 0;
  val_0.total = 1;
  fill(check, check + MAXN, false);
  sort(query.begin(), query.end(), std::greater<pair<long long, long long> >());
  for (long long i = 0; i < query.size(); i++) {
    long long id = query[i].second;
    if (id > 0) {
      check[st[id]] = true;
      update(0, 1, n, st[id]);
    } else {
      ans[-id] = solve(s[-id], e[-id]).res;
    }
  }
  for (long long i = 0; i < q; i++) {
    cout << ans[i] << endl;
  }
}

### 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 long long MAXN = 1e5 + 10;
struct node {
  long long res, pre, suf, total;
  node() {
    res = 0;
    pre = 0;
    suf = 0;
    total = 0;
  }
};
node segt[4 * MAXN];
vector<pair<long long, long long> > vertex[MAXN];
vector<pair<long long, long long> > query;
long long s[MAXN];
long long e[MAXN];
long long f[MAXN];
long long st[MAXN];
long long ft[MAXN];
long long up[MAXN];
long long par[MAXN];
long long len[MAXN];
long long ans[MAXN];
long long subtree[MAXN];
bool check[MAXN];
node val_0, val_1;
long long n, t = 0;
bool cmp(const pair<long long, long long>& x,
         const pair<long long, long long>& y) {
  return subtree[x.first] > subtree[y.first];
}
bool is_par(const long long& v, const long long& u) {
  return (st[v] <= st[u] && ft[v] >= ft[u]);
}
void set_dfs(long long v) {
  check[v] = true;
  subtree[v] = 1;
  for (long long i = 0; i < vertex[v].size(); i++) {
    if (!check[vertex[v][i].first]) {
      par[vertex[v][i].first] = v;
      query.push_back(make_pair(vertex[v][i].second, vertex[v][i].first));
      set_dfs(vertex[v][i].first);
      subtree[v] += subtree[vertex[v][i].first];
    }
  }
}
void set_time_dfs(long long v, long long u) {
  check[v] = true;
  st[v] = ++t;
  up[v] = u;
  bool flag = false;
  for (long long i = 0; i < vertex[v].size(); i++) {
    if (!check[vertex[v][i].first]) {
      if (!flag) {
        set_time_dfs(vertex[v][i].first, u);
      } else {
        set_time_dfs(vertex[v][i].first, vertex[v][i].first);
      }
      flag = true;
    }
  }
  ft[v] = t;
}
node merge_node(node x, node y) {
  node res;
  res.res = x.res + y.res + f[x.suf + y.pre] - f[x.suf] - f[y.pre];
  res.pre = (x.pre == x.total ? y.pre + x.total : x.pre);
  res.suf = (y.suf == y.total ? x.suf + y.total : y.suf);
  res.total = x.total + y.total;
  return res;
}
void build(long long id, long long L, long long R) {
  if (L == R) {
    segt[id].total = 1;
    return;
  }
  long long mid = (L + R) / 2;
  build(2 * id + 1, L, mid);
  build(2 * id + 2, mid + 1, R);
  segt[id] = merge_node(segt[2 * id + 1], segt[2 * id + 2]);
}
void update(long long id, long long L, long long R, long long p) {
  if (R < L || p < L || p > R) {
    return;
  }
  if (L == R) {
    segt[id].res = f[1];
    segt[id].pre = 1;
    segt[id].suf = 1;
    segt[id].total = 1;
    return;
  }
  long long mid = (L + R) / 2;
  update(2 * id + 1, L, mid, p);
  update(2 * id + 2, mid + 1, R, p);
  segt[id] = merge_node(segt[2 * id + 1], segt[2 * id + 2]);
}
node get_res(long long id, long long L, long long R, long long l, long long r) {
  if (R < L || L > r || R < l) {
    node res;
    return res;
  }
  if (L >= l && R <= r) {
    return segt[id];
  }
  long long mid = (L + R) / 2;
  return merge_node(get_res(2 * id + 1, L, mid, l, r),
                    get_res(2 * id + 2, mid + 1, R, l, r));
}
node solve(long long v, long long u) {
  node res_v, res_u;
  while (!is_par(up[v], u)) {
    node k = get_res(0, 1, n, st[up[v]] + 1, st[v]);
    swap(k.pre, k.suf);
    res_v = merge_node(res_v, k);
    v = up[v];
    if (check[st[v]]) {
      res_v = merge_node(res_v, val_1);
    } else {
      res_v = merge_node(res_v, val_0);
    }
    v = par[v];
  }
  while (!is_par(up[u], v)) {
    res_u = merge_node(get_res(0, 1, n, st[up[u]] + 1, st[u]), res_u);
    u = up[u];
    if (check[st[u]]) {
      res_u = merge_node(val_1, res_u);
    } else {
      res_u = merge_node(val_0, res_u);
    }
    u = par[u];
  }
  if (is_par(u, v)) {
    node k = get_res(0, 1, n, st[u] + 1, st[v]);
    swap(k.pre, k.suf);
    res_u = merge_node(k, res_u);
  } else {
    node k = get_res(0, 1, n, st[v] + 1, st[u]);
    res_v = merge_node(res_v, k);
  }
  return merge_node(res_v, res_u);
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  long long q;
  cin >> n >> q;
  for (long long i = 1; i < n; i++) {
    cin >> f[i];
  }
  for (long long i = 0; i < (n - 1); i++) {
    long long v, u, w;
    cin >> v >> u >> w;
    vertex[v].push_back(make_pair(u, w));
    vertex[u].push_back(make_pair(v, w));
  }
  set_dfs(1);
  for (long long i = 1; i <= n; i++) {
    check[i] = false;
    sort(vertex[i].begin(), vertex[i].end(), cmp);
  }
  par[1] = 1;
  set_time_dfs(1, 1);
  for (long long i = 0; i < q; i++) {
    cin >> s[i] >> e[i] >> len[i];
    query.push_back(make_pair(len[i], -i));
  }
  build(0, 1, n);
  val_1.res = f[1];
  val_1.pre = 1;
  val_1.suf = 1;
  val_1.total = 1;
  val_0.res = 0;
  val_0.pre = 0;
  val_0.suf = 0;
  val_0.total = 1;
  fill(check, check + MAXN, false);
  sort(query.begin(), query.end(), std::greater<pair<long long, long long> >());
  for (long long i = 0; i < query.size(); i++) {
    long long id = query[i].second;
    if (id > 0) {
      check[st[id]] = true;
      update(0, 1, n, st[id]);
    } else {
      ans[-id] = solve(s[-id], e[-id]).res;
    }
  }
  for (long long i = 0; i < q; i++) {
    cout << ans[i] << endl;
  }
}

```