#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
const int LOG = 17;
struct edge {
  int to;
  int weight;
};
int block_cost[N];
vector<edge> edges[N];
vector<int> vertexes[N];
int block_cnt;
int children[N];
int block_pos[N];
int block_num[N];
edge up[N];
int top[N][LOG];
int parent[N];
int comp_size[N];
bool used[N];
vector<vector<int> > value[N];
vector<vector<int> > toleft[N];
vector<vector<int> > toright[N];
vector<vector<int> > add[N];
int depth[N];
int head[N];
int get_parent(int x) {
  return (parent[x] == x ? x : parent[x] = get_parent(parent[x]));
}
void unite(int x, int y) {
  if (comp_size[x] < comp_size[y]) {
    swap(x, y);
  }
  parent[y] = x;
  comp_size[x] += comp_size[y];
}
void dfs(int x, int pred) {
  depth[x] = depth[pred] + 1;
  top[x][0] = pred;
  for (int i = 1; i < LOG; i++) {
    top[x][i] = top[top[x][i - 1]][i - 1];
  }
  children[x] = 1;
  for (size_t i = 0; i < edges[x].size(); i++) {
    int to = edges[x][i].to;
    if (to == pred) {
      continue;
    }
    up[to].to = x;
    up[to].weight = edges[x][i].weight;
    dfs(to, x);
    children[x] += children[to];
  }
}
void heavy_light_decomposition(int x, int number) {
  block_pos[x] = (int)vertexes[number].size();
  block_num[x] = number;
  if (vertexes[number].size() == 0) {
    head[number] = x;
  }
  vertexes[number].push_back(up[x].weight);
  if (children[x] == 1) {
    return;
  }
  int go = -1;
  for (size_t i = 0; i < edges[x].size(); i++) {
    int to = edges[x][i].to;
    if (to == up[x].to) {
      continue;
    }
    if (go == -1 || children[go] < children[to]) {
      go = to;
    }
  }
  heavy_light_decomposition(go, number);
  for (size_t i = 0; i < edges[x].size(); i++) {
    int to = edges[x][i].to;
    if (to == up[x].to || to == go) {
      continue;
    }
    heavy_light_decomposition(to, ++block_cnt);
  }
}
void build(int nom, int i, int l, int r) {
  value[nom][i].resize(r - l + 1);
  toleft[nom][i].resize(r - l + 1);
  toright[nom][i].resize(r - l + 1);
  add[nom][i].resize(r - l + 1);
  if (l == r) {
    value[nom][i][0] = l;
    toleft[nom][i][0] = 1;
    toright[nom][i][0] = 1;
    add[nom][i][0] = block_cost[1];
    return;
  }
  int m = (l + r) / 2;
  build(nom, i * 2, l, m);
  build(nom, i * 2 + 1, m + 1, r);
  for (int j = l - 1; j <= r + 1; j++) {
    used[j] = false;
    parent[j] = j;
    comp_size[j] = 1;
  }
  int i1 = 0;
  int i2 = 0;
  int s1 = (int)value[nom][i * 2].size();
  int s2 = (int)value[nom][i * 2 + 1].size();
  int res = 0;
  for (size_t j = 0; j < value[nom][i].size(); j++) {
    int ps;
    if (i1 != s1 &&
        (i2 == s2 || vertexes[nom][value[nom][i * 2][i1]] >
                         vertexes[nom][value[nom][i * 2 + 1][i2]])) {
      ps = value[nom][i * 2][i1++];
    } else {
      ps = value[nom][i * 2 + 1][i2++];
    }
    value[nom][i][j] = ps;
    used[ps] = true;
    if (used[ps - 1]) {
      int lleft = get_parent(ps - 1);
      res -= block_cost[comp_size[lleft]];
      unite(get_parent(ps), lleft);
    }
    if (used[ps + 1]) {
      int rright = get_parent(ps + 1);
      res -= block_cost[comp_size[rright]];
      unite(get_parent(ps), rright);
    }
    res += block_cost[comp_size[get_parent(ps)]];
    toleft[nom][i][j] = (used[l] ? comp_size[get_parent(l)] : 0);
    toright[nom][i][j] = (used[r] ? comp_size[get_parent(r)] : 0);
    add[nom][i][j] = res;
  }
}
void join(int l1, int tl1, int tr1, int s1, int l2, int tl2, int tr2, int s2,
          int &l3, int &tl3, int &tr3, int &s3) {
  l3 = l1 + l2;
  if (l1 == tl1 && l2 == tl2) {
    tl3 = l3;
    tr3 = l3;
    s3 = block_cost[l3];
    return;
  }
  if (l1 == tl1) {
    tl3 = l1 + tl2;
    tr3 = tr2;
    s3 = s1 + s2 - block_cost[l1] - block_cost[tl2] + block_cost[tl3];
    return;
  }
  if (l2 == tl2) {
    tl3 = tl1;
    tr3 = tr1 + l2;
    s3 = s1 + s2 - block_cost[tr1] - block_cost[l2] + block_cost[tr3];
    return;
  }
  tl3 = tl1;
  tr3 = tr2;
  s3 = s1 + s2 - block_cost[tr1] - block_cost[tl2] + block_cost[tr1 + tl2];
}
void get(int nom, int i, int l, int r, int ql, int qr, int limit, int &l3,
         int &tl3, int &tr3, int &s3) {
  if (l == ql && r == qr) {
    l3 = r - l + 1;
    if (limit > vertexes[nom][value[nom][i][0]]) {
      tl3 = 0;
      tr3 = 0;
      s3 = 0;
      return;
    }
    int left = 0, right = (int)value[nom][i].size();
    while (right - left > 1) {
      int middle = (left + right) / 2;
      if (limit <= vertexes[nom][value[nom][i][middle]]) {
        left = middle;
      } else {
        right = middle;
      }
    }
    tl3 = toleft[nom][i][left];
    tr3 = toright[nom][i][left];
    s3 = add[nom][i][left];
    return;
  }
  int m = (l + r) / 2;
  bool ok_left = false;
  bool ok_right = false;
  int l1 = 0;
  int tl1 = 0;
  int tr1 = 0;
  int s1 = 0;
  int l2 = 0;
  int tl2 = 0;
  int tr2 = 0;
  int s2 = 0;
  if (ql <= m) {
    ok_left = true;
    get(nom, i * 2, l, m, ql, min(qr, m), limit, l1, tl1, tr1, s1);
  }
  if (m < qr) {
    ok_right = true;
    get(nom, i * 2 + 1, m + 1, r, max(ql, m + 1), qr, limit, l2, tl2, tr2, s2);
  }
  if (ok_left && ok_right) {
    join(l1, tl1, tr1, s1, l2, tl2, tr2, s2, l3, tl3, tr3, s3);
  } else if (ok_left) {
    l3 = l1;
    tl3 = tl1;
    tr3 = tr1;
    s3 = s1;
  } else {
    l3 = l2;
    tl3 = tl2;
    tr3 = tr2;
    s3 = s2;
  }
}
void query(int limit, int x, int need, int &ll, int &tl, int &tr, int &sum) {
  int l1;
  int tl1;
  int tr1;
  int sum1;
  ll = 0;
  tl = 0;
  tr = 0;
  sum = 0;
  while (block_num[x] != block_num[need]) {
    if (block_pos[x] != 0) {
      get(block_num[x], 1, 1, (int)vertexes[block_num[x]].size() - 1, 1,
          block_pos[x], limit, l1, tl1, tr1, sum1);
      join(l1, tl1, tr1, sum1, ll, tl, tr, sum, ll, tl, tr, sum);
    }
    x = head[block_num[x]];
    if (limit <= up[x].weight) {
      l1 = 1;
      tl1 = 1;
      tr1 = 1;
      sum1 = block_cost[1];
    } else {
      l1 = 1;
      tl1 = 0;
      tr1 = 0;
      sum1 = 0;
    }
    x = up[x].to;
    join(l1, tl1, tr1, sum1, ll, tl, tr, sum, ll, tl, tr, sum);
  }
  if (block_pos[x] != block_pos[need]) {
    get(block_num[x], 1, 1, (int)vertexes[block_num[x]].size() - 1,
        block_pos[need] + 1, block_pos[x], limit, l1, tl1, tr1, sum1);
    join(l1, tl1, tr1, sum1, ll, tl, tr, sum, ll, tl, tr, sum);
  }
}
int main() {
  int n;
  int q;
  scanf("%d %d", &n, &q);
  for (int i = 1; i < n; i++) {
    scanf("%d", &block_cost[i]);
  }
  for (int i = 1; i < n; i++) {
    int v;
    int u;
    int w;
    scanf("%d %d %d", &u, &v, &w);
    edges[u].push_back({v, w});
    edges[v].push_back({u, w});
  }
  depth[1] = 0;
  dfs(1, 1);
  block_cnt = 1;
  heavy_light_decomposition(1, 1);
  for (int i = 1; i <= block_cnt; i++) {
    int limit = (int)vertexes[i].size();
    value[i].resize(4 * limit);
    toleft[i].resize(4 * limit);
    toright[i].resize(4 * limit);
    add[i].resize(4 * limit);
    if (limit == 1) {
      continue;
    }
    build(i, 1, 1, limit - 1);
  }
  for (int q_cur = 1; q_cur <= q; q_cur++) {
    int v;
    int u;
    int limit;
    scanf("%d %d %d", &v, &u, &limit);
    if (depth[v] > depth[u]) {
      swap(v, u);
    }
    int hv = v;
    int hu = u;
    int difference = depth[hu] - depth[hv];
    for (int i = 0; i < LOG; i++) {
      if (difference & (1 << i)) {
        hu = top[hu][i];
      }
    }
    int lca;
    if (hu == hv) {
      lca = hu;
    } else {
      for (int i = LOG - 1; i >= 0; i--) {
        if (top[hu][i] != top[hv][i]) {
          hu = top[hu][i];
          hv = top[hv][i];
        }
      }
      lca = top[hu][0];
    }
    int l1;
    int tl1;
    int tr1;
    int sum1;
    int l2;
    int tl2;
    int tr2;
    int sum2;
    int l3;
    int tl3;
    int tr3;
    int sum3;
    query(limit, v, lca, l1, tl1, tr1, sum1);
    query(limit, u, lca, l2, tl2, tr2, sum2);
    join(l1, tr1, tl1, sum1, l2, tl2, tr2, sum2, l3, tl3, tr3, sum3);
    printf("%d\n", sum3);
  }
  return 0;
}

### Prompt

Create a solution in CPP for 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 = 100000 + 10;
const int LOG = 17;
struct edge {
  int to;
  int weight;
};
int block_cost[N];
vector<edge> edges[N];
vector<int> vertexes[N];
int block_cnt;
int children[N];
int block_pos[N];
int block_num[N];
edge up[N];
int top[N][LOG];
int parent[N];
int comp_size[N];
bool used[N];
vector<vector<int> > value[N];
vector<vector<int> > toleft[N];
vector<vector<int> > toright[N];
vector<vector<int> > add[N];
int depth[N];
int head[N];
int get_parent(int x) {
  return (parent[x] == x ? x : parent[x] = get_parent(parent[x]));
}
void unite(int x, int y) {
  if (comp_size[x] < comp_size[y]) {
    swap(x, y);
  }
  parent[y] = x;
  comp_size[x] += comp_size[y];
}
void dfs(int x, int pred) {
  depth[x] = depth[pred] + 1;
  top[x][0] = pred;
  for (int i = 1; i < LOG; i++) {
    top[x][i] = top[top[x][i - 1]][i - 1];
  }
  children[x] = 1;
  for (size_t i = 0; i < edges[x].size(); i++) {
    int to = edges[x][i].to;
    if (to == pred) {
      continue;
    }
    up[to].to = x;
    up[to].weight = edges[x][i].weight;
    dfs(to, x);
    children[x] += children[to];
  }
}
void heavy_light_decomposition(int x, int number) {
  block_pos[x] = (int)vertexes[number].size();
  block_num[x] = number;
  if (vertexes[number].size() == 0) {
    head[number] = x;
  }
  vertexes[number].push_back(up[x].weight);
  if (children[x] == 1) {
    return;
  }
  int go = -1;
  for (size_t i = 0; i < edges[x].size(); i++) {
    int to = edges[x][i].to;
    if (to == up[x].to) {
      continue;
    }
    if (go == -1 || children[go] < children[to]) {
      go = to;
    }
  }
  heavy_light_decomposition(go, number);
  for (size_t i = 0; i < edges[x].size(); i++) {
    int to = edges[x][i].to;
    if (to == up[x].to || to == go) {
      continue;
    }
    heavy_light_decomposition(to, ++block_cnt);
  }
}
void build(int nom, int i, int l, int r) {
  value[nom][i].resize(r - l + 1);
  toleft[nom][i].resize(r - l + 1);
  toright[nom][i].resize(r - l + 1);
  add[nom][i].resize(r - l + 1);
  if (l == r) {
    value[nom][i][0] = l;
    toleft[nom][i][0] = 1;
    toright[nom][i][0] = 1;
    add[nom][i][0] = block_cost[1];
    return;
  }
  int m = (l + r) / 2;
  build(nom, i * 2, l, m);
  build(nom, i * 2 + 1, m + 1, r);
  for (int j = l - 1; j <= r + 1; j++) {
    used[j] = false;
    parent[j] = j;
    comp_size[j] = 1;
  }
  int i1 = 0;
  int i2 = 0;
  int s1 = (int)value[nom][i * 2].size();
  int s2 = (int)value[nom][i * 2 + 1].size();
  int res = 0;
  for (size_t j = 0; j < value[nom][i].size(); j++) {
    int ps;
    if (i1 != s1 &&
        (i2 == s2 || vertexes[nom][value[nom][i * 2][i1]] >
                         vertexes[nom][value[nom][i * 2 + 1][i2]])) {
      ps = value[nom][i * 2][i1++];
    } else {
      ps = value[nom][i * 2 + 1][i2++];
    }
    value[nom][i][j] = ps;
    used[ps] = true;
    if (used[ps - 1]) {
      int lleft = get_parent(ps - 1);
      res -= block_cost[comp_size[lleft]];
      unite(get_parent(ps), lleft);
    }
    if (used[ps + 1]) {
      int rright = get_parent(ps + 1);
      res -= block_cost[comp_size[rright]];
      unite(get_parent(ps), rright);
    }
    res += block_cost[comp_size[get_parent(ps)]];
    toleft[nom][i][j] = (used[l] ? comp_size[get_parent(l)] : 0);
    toright[nom][i][j] = (used[r] ? comp_size[get_parent(r)] : 0);
    add[nom][i][j] = res;
  }
}
void join(int l1, int tl1, int tr1, int s1, int l2, int tl2, int tr2, int s2,
          int &l3, int &tl3, int &tr3, int &s3) {
  l3 = l1 + l2;
  if (l1 == tl1 && l2 == tl2) {
    tl3 = l3;
    tr3 = l3;
    s3 = block_cost[l3];
    return;
  }
  if (l1 == tl1) {
    tl3 = l1 + tl2;
    tr3 = tr2;
    s3 = s1 + s2 - block_cost[l1] - block_cost[tl2] + block_cost[tl3];
    return;
  }
  if (l2 == tl2) {
    tl3 = tl1;
    tr3 = tr1 + l2;
    s3 = s1 + s2 - block_cost[tr1] - block_cost[l2] + block_cost[tr3];
    return;
  }
  tl3 = tl1;
  tr3 = tr2;
  s3 = s1 + s2 - block_cost[tr1] - block_cost[tl2] + block_cost[tr1 + tl2];
}
void get(int nom, int i, int l, int r, int ql, int qr, int limit, int &l3,
         int &tl3, int &tr3, int &s3) {
  if (l == ql && r == qr) {
    l3 = r - l + 1;
    if (limit > vertexes[nom][value[nom][i][0]]) {
      tl3 = 0;
      tr3 = 0;
      s3 = 0;
      return;
    }
    int left = 0, right = (int)value[nom][i].size();
    while (right - left > 1) {
      int middle = (left + right) / 2;
      if (limit <= vertexes[nom][value[nom][i][middle]]) {
        left = middle;
      } else {
        right = middle;
      }
    }
    tl3 = toleft[nom][i][left];
    tr3 = toright[nom][i][left];
    s3 = add[nom][i][left];
    return;
  }
  int m = (l + r) / 2;
  bool ok_left = false;
  bool ok_right = false;
  int l1 = 0;
  int tl1 = 0;
  int tr1 = 0;
  int s1 = 0;
  int l2 = 0;
  int tl2 = 0;
  int tr2 = 0;
  int s2 = 0;
  if (ql <= m) {
    ok_left = true;
    get(nom, i * 2, l, m, ql, min(qr, m), limit, l1, tl1, tr1, s1);
  }
  if (m < qr) {
    ok_right = true;
    get(nom, i * 2 + 1, m + 1, r, max(ql, m + 1), qr, limit, l2, tl2, tr2, s2);
  }
  if (ok_left && ok_right) {
    join(l1, tl1, tr1, s1, l2, tl2, tr2, s2, l3, tl3, tr3, s3);
  } else if (ok_left) {
    l3 = l1;
    tl3 = tl1;
    tr3 = tr1;
    s3 = s1;
  } else {
    l3 = l2;
    tl3 = tl2;
    tr3 = tr2;
    s3 = s2;
  }
}
void query(int limit, int x, int need, int &ll, int &tl, int &tr, int &sum) {
  int l1;
  int tl1;
  int tr1;
  int sum1;
  ll = 0;
  tl = 0;
  tr = 0;
  sum = 0;
  while (block_num[x] != block_num[need]) {
    if (block_pos[x] != 0) {
      get(block_num[x], 1, 1, (int)vertexes[block_num[x]].size() - 1, 1,
          block_pos[x], limit, l1, tl1, tr1, sum1);
      join(l1, tl1, tr1, sum1, ll, tl, tr, sum, ll, tl, tr, sum);
    }
    x = head[block_num[x]];
    if (limit <= up[x].weight) {
      l1 = 1;
      tl1 = 1;
      tr1 = 1;
      sum1 = block_cost[1];
    } else {
      l1 = 1;
      tl1 = 0;
      tr1 = 0;
      sum1 = 0;
    }
    x = up[x].to;
    join(l1, tl1, tr1, sum1, ll, tl, tr, sum, ll, tl, tr, sum);
  }
  if (block_pos[x] != block_pos[need]) {
    get(block_num[x], 1, 1, (int)vertexes[block_num[x]].size() - 1,
        block_pos[need] + 1, block_pos[x], limit, l1, tl1, tr1, sum1);
    join(l1, tl1, tr1, sum1, ll, tl, tr, sum, ll, tl, tr, sum);
  }
}
int main() {
  int n;
  int q;
  scanf("%d %d", &n, &q);
  for (int i = 1; i < n; i++) {
    scanf("%d", &block_cost[i]);
  }
  for (int i = 1; i < n; i++) {
    int v;
    int u;
    int w;
    scanf("%d %d %d", &u, &v, &w);
    edges[u].push_back({v, w});
    edges[v].push_back({u, w});
  }
  depth[1] = 0;
  dfs(1, 1);
  block_cnt = 1;
  heavy_light_decomposition(1, 1);
  for (int i = 1; i <= block_cnt; i++) {
    int limit = (int)vertexes[i].size();
    value[i].resize(4 * limit);
    toleft[i].resize(4 * limit);
    toright[i].resize(4 * limit);
    add[i].resize(4 * limit);
    if (limit == 1) {
      continue;
    }
    build(i, 1, 1, limit - 1);
  }
  for (int q_cur = 1; q_cur <= q; q_cur++) {
    int v;
    int u;
    int limit;
    scanf("%d %d %d", &v, &u, &limit);
    if (depth[v] > depth[u]) {
      swap(v, u);
    }
    int hv = v;
    int hu = u;
    int difference = depth[hu] - depth[hv];
    for (int i = 0; i < LOG; i++) {
      if (difference & (1 << i)) {
        hu = top[hu][i];
      }
    }
    int lca;
    if (hu == hv) {
      lca = hu;
    } else {
      for (int i = LOG - 1; i >= 0; i--) {
        if (top[hu][i] != top[hv][i]) {
          hu = top[hu][i];
          hv = top[hv][i];
        }
      }
      lca = top[hu][0];
    }
    int l1;
    int tl1;
    int tr1;
    int sum1;
    int l2;
    int tl2;
    int tr2;
    int sum2;
    int l3;
    int tl3;
    int tr3;
    int sum3;
    query(limit, v, lca, l1, tl1, tr1, sum1);
    query(limit, u, lca, l2, tl2, tr2, sum2);
    join(l1, tr1, tl1, sum1, l2, tl2, tr2, sum2, l3, tl3, tr3, sum3);
    printf("%d\n", sum3);
  }
  return 0;
}

```