#include <bits/stdc++.h>
using namespace std;
struct query {
  int time, l, v1, v2;
  bool operator<(const query &q) const { return l < q.l; }
  query(int time, int l, int v1, int v2) : time(time), l(l), v1(v1), v2(v2) {}
  query() {}
};
int n, m, j, i, h, k, q1, q2, q, l, high[100500], own[100500], par[100500],
    lvl[100500], cnt[100500], f[100500], nxt[100500], ans[100500], ptr;
vector<pair<int, int> > g[100500];
query qu[100500];
vector<pair<int, int> > dist;
struct node {
  int l, r, mid, size;
  node(int mid, int l, int r, int size) : mid(mid), size(size), l(l), r(r) {}
  node() {}
  node operator+(const node &n) {
    node res;
    if (size == l) {
      if (n.size == n.l) {
        return node(0, l + n.l, r + n.r, size + n.size);
      } else {
        return node(n.mid, l + n.l, n.r, size + n.size);
      }
    } else {
      if (n.size == n.l) {
        return node(mid, l, r + n.r, size + n.size);
      } else {
        return node(mid + n.mid + f[r + n.l], l, n.r, size + n.size);
      }
    }
  }
  node operator!() {
    node res = (*this);
    swap(res.l, res.r);
    return res;
  }
  int answer() {
    if (l != size) {
      return f[l] + mid + f[r];
    } else {
      return f[l];
    }
  }
};
struct segment_tree {
 private:
  vector<node> tree;
  int size;
  void update(int i, int p1, int p2, int q) {
    if (p1 == p2) {
      tree[i] = node(0, 0, 0, 1);
      return;
    }
    int p = (p1 + p2) >> 1;
    if (q <= p) {
      update((i << 1) + 1, p1, p, q);
    } else {
      update((i << 1) + 2, p + 1, p2, q);
    }
    tree[i] = tree[(i << 1) + 1] + tree[(i << 1) + 2];
  }
  void build(int i, int p1, int p2) {
    if (p1 == p2) {
      tree[i] = node(0, 1, 1, 1);
      return;
    }
    int p = (p1 + p2) >> 1;
    build((i << 1) + 1, p1, p);
    build((i << 1) + 2, p + 1, p2);
    tree[i] = tree[(i << 1) + 1] + tree[(i << 1) + 2];
  }
  node get_sum(int i, int p1, int p2, int q1, int q2) {
    if (q1 <= p1 && p2 <= q2) {
      return tree[i];
    }
    int p = (p1 + p2) >> 1;
    node res(0, 0, 0, 0);
    if (q1 <= p) {
      res = res + get_sum((i << 1) + 1, p1, p, q1, q2);
    }
    if (q2 > p) {
      res = res + get_sum((i << 1) + 2, p + 1, p2, q1, q2);
    }
    return res;
  }

 public:
  segment_tree() {}
  segment_tree(int v, int len) {
    tree.resize(len << 2);
    size = len;
    build(0, 0, len - 1);
  }
  void update(int pos) { update(0, 0, size - 1, pos); }
  node get_sum(int pos1, int pos2) {
    return get_sum(0, 0, size - 1, pos1, pos2);
  }
};
segment_tree trees[100500];
void init_dfs(int v, int p) {
  par[v] = p;
  cnt[v] = 1;
  lvl[v] = lvl[p] + 1;
  for (int j = 0; j < g[v].size(); j++) {
    if (g[v][j].first == p) {
      continue;
    }
    init_dfs(g[v][j].first, v);
    cnt[v] += cnt[g[v][j].first];
    if (cnt[g[v][j].first] > cnt[nxt[v]]) {
      nxt[v] = g[v][j].first;
    }
    dist.push_back(pair<int, int>(g[v][j].second, g[v][j].first));
  }
}
int build_dfs(int v, int top_v) {
  high[v] = top_v;
  if (!nxt[v]) {
    trees[v] = segment_tree(v, lvl[v] - lvl[top_v]);
    return own[v] = v;
  }
  for (int j = 0; j < g[v].size(); j++) {
    if (g[v][j].first == par[v]) {
      continue;
    }
    if (g[v][j].first == nxt[v]) {
      own[v] = build_dfs(nxt[v], top_v);
      continue;
    }
    build_dfs(g[v][j].first, v);
  }
  return own[v];
}
void solve() {
  scanf("%d%d", &n, &m);
  for (j = 1; j < n; j++) {
    scanf("%d", &f[j]);
  }
  for (j = 1; j < n; j++) {
    scanf("%d%d%d", &q1, &q2, &q);
    g[q1].push_back(pair<int, int>(q2, q));
    g[q2].push_back(pair<int, int>(q1, q));
  }
  init_dfs(1, 0);
  build_dfs(1, 0);
  sort(dist.begin(), dist.end());
  for (j = 1; j <= m; j++) {
    scanf("%d%d%d", &q1, &q2, &q);
    qu[j] = query(j, q, q1, q2);
  }
  sort(qu + 1, qu + m + 1);
  for (j = 1; j <= m; j++) {
    while (ptr < dist.size() && dist[ptr].first < qu[j].l) {
      trees[own[dist[ptr].second]].update(lvl[own[dist[ptr].second]] -
                                          lvl[dist[ptr].second]);
      ptr++;
    }
    q1 = qu[j].v1;
    q2 = qu[j].v2;
    node res1 = node(0, 0, 0, 0), res2 = node(0, 0, 0, 0);
    while (own[q1] != own[q2]) {
      int top1 = high[q1], top2 = high[q2];
      if (lvl[top1] >= lvl[top2]) {
        res1 = res1 + trees[own[q1]].get_sum(lvl[own[q1]] - lvl[q1],
                                             lvl[own[q1]] - lvl[top1] - 1);
        q1 = top1;
      } else {
        res2 = res2 + trees[own[q2]].get_sum(lvl[own[q2]] - lvl[q2],
                                             lvl[own[q2]] - lvl[top2] - 1);
        q2 = top2;
      }
    }
    if (q1 != q2) {
      if (lvl[q1] > lvl[q2]) {
        res1 = res1 + trees[own[q1]].get_sum(lvl[own[q1]] - lvl[q1],
                                             lvl[own[q1]] - lvl[q2] - 1);
      } else {
        res2 = res2 + trees[own[q2]].get_sum(lvl[own[q2]] - lvl[q2],
                                             lvl[own[q2]] - lvl[q1] - 1);
      }
    }
    res1 = res1 + !res2;
    ans[qu[j].time] = res1.answer();
  }
  for (j = 1; j <= m; j++) {
    printf("%d\n", ans[j]);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  srand(333);
  solve();
  return 0;
}

### 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;
struct query {
  int time, l, v1, v2;
  bool operator<(const query &q) const { return l < q.l; }
  query(int time, int l, int v1, int v2) : time(time), l(l), v1(v1), v2(v2) {}
  query() {}
};
int n, m, j, i, h, k, q1, q2, q, l, high[100500], own[100500], par[100500],
    lvl[100500], cnt[100500], f[100500], nxt[100500], ans[100500], ptr;
vector<pair<int, int> > g[100500];
query qu[100500];
vector<pair<int, int> > dist;
struct node {
  int l, r, mid, size;
  node(int mid, int l, int r, int size) : mid(mid), size(size), l(l), r(r) {}
  node() {}
  node operator+(const node &n) {
    node res;
    if (size == l) {
      if (n.size == n.l) {
        return node(0, l + n.l, r + n.r, size + n.size);
      } else {
        return node(n.mid, l + n.l, n.r, size + n.size);
      }
    } else {
      if (n.size == n.l) {
        return node(mid, l, r + n.r, size + n.size);
      } else {
        return node(mid + n.mid + f[r + n.l], l, n.r, size + n.size);
      }
    }
  }
  node operator!() {
    node res = (*this);
    swap(res.l, res.r);
    return res;
  }
  int answer() {
    if (l != size) {
      return f[l] + mid + f[r];
    } else {
      return f[l];
    }
  }
};
struct segment_tree {
 private:
  vector<node> tree;
  int size;
  void update(int i, int p1, int p2, int q) {
    if (p1 == p2) {
      tree[i] = node(0, 0, 0, 1);
      return;
    }
    int p = (p1 + p2) >> 1;
    if (q <= p) {
      update((i << 1) + 1, p1, p, q);
    } else {
      update((i << 1) + 2, p + 1, p2, q);
    }
    tree[i] = tree[(i << 1) + 1] + tree[(i << 1) + 2];
  }
  void build(int i, int p1, int p2) {
    if (p1 == p2) {
      tree[i] = node(0, 1, 1, 1);
      return;
    }
    int p = (p1 + p2) >> 1;
    build((i << 1) + 1, p1, p);
    build((i << 1) + 2, p + 1, p2);
    tree[i] = tree[(i << 1) + 1] + tree[(i << 1) + 2];
  }
  node get_sum(int i, int p1, int p2, int q1, int q2) {
    if (q1 <= p1 && p2 <= q2) {
      return tree[i];
    }
    int p = (p1 + p2) >> 1;
    node res(0, 0, 0, 0);
    if (q1 <= p) {
      res = res + get_sum((i << 1) + 1, p1, p, q1, q2);
    }
    if (q2 > p) {
      res = res + get_sum((i << 1) + 2, p + 1, p2, q1, q2);
    }
    return res;
  }

 public:
  segment_tree() {}
  segment_tree(int v, int len) {
    tree.resize(len << 2);
    size = len;
    build(0, 0, len - 1);
  }
  void update(int pos) { update(0, 0, size - 1, pos); }
  node get_sum(int pos1, int pos2) {
    return get_sum(0, 0, size - 1, pos1, pos2);
  }
};
segment_tree trees[100500];
void init_dfs(int v, int p) {
  par[v] = p;
  cnt[v] = 1;
  lvl[v] = lvl[p] + 1;
  for (int j = 0; j < g[v].size(); j++) {
    if (g[v][j].first == p) {
      continue;
    }
    init_dfs(g[v][j].first, v);
    cnt[v] += cnt[g[v][j].first];
    if (cnt[g[v][j].first] > cnt[nxt[v]]) {
      nxt[v] = g[v][j].first;
    }
    dist.push_back(pair<int, int>(g[v][j].second, g[v][j].first));
  }
}
int build_dfs(int v, int top_v) {
  high[v] = top_v;
  if (!nxt[v]) {
    trees[v] = segment_tree(v, lvl[v] - lvl[top_v]);
    return own[v] = v;
  }
  for (int j = 0; j < g[v].size(); j++) {
    if (g[v][j].first == par[v]) {
      continue;
    }
    if (g[v][j].first == nxt[v]) {
      own[v] = build_dfs(nxt[v], top_v);
      continue;
    }
    build_dfs(g[v][j].first, v);
  }
  return own[v];
}
void solve() {
  scanf("%d%d", &n, &m);
  for (j = 1; j < n; j++) {
    scanf("%d", &f[j]);
  }
  for (j = 1; j < n; j++) {
    scanf("%d%d%d", &q1, &q2, &q);
    g[q1].push_back(pair<int, int>(q2, q));
    g[q2].push_back(pair<int, int>(q1, q));
  }
  init_dfs(1, 0);
  build_dfs(1, 0);
  sort(dist.begin(), dist.end());
  for (j = 1; j <= m; j++) {
    scanf("%d%d%d", &q1, &q2, &q);
    qu[j] = query(j, q, q1, q2);
  }
  sort(qu + 1, qu + m + 1);
  for (j = 1; j <= m; j++) {
    while (ptr < dist.size() && dist[ptr].first < qu[j].l) {
      trees[own[dist[ptr].second]].update(lvl[own[dist[ptr].second]] -
                                          lvl[dist[ptr].second]);
      ptr++;
    }
    q1 = qu[j].v1;
    q2 = qu[j].v2;
    node res1 = node(0, 0, 0, 0), res2 = node(0, 0, 0, 0);
    while (own[q1] != own[q2]) {
      int top1 = high[q1], top2 = high[q2];
      if (lvl[top1] >= lvl[top2]) {
        res1 = res1 + trees[own[q1]].get_sum(lvl[own[q1]] - lvl[q1],
                                             lvl[own[q1]] - lvl[top1] - 1);
        q1 = top1;
      } else {
        res2 = res2 + trees[own[q2]].get_sum(lvl[own[q2]] - lvl[q2],
                                             lvl[own[q2]] - lvl[top2] - 1);
        q2 = top2;
      }
    }
    if (q1 != q2) {
      if (lvl[q1] > lvl[q2]) {
        res1 = res1 + trees[own[q1]].get_sum(lvl[own[q1]] - lvl[q1],
                                             lvl[own[q1]] - lvl[q2] - 1);
      } else {
        res2 = res2 + trees[own[q2]].get_sum(lvl[own[q2]] - lvl[q2],
                                             lvl[own[q2]] - lvl[q1] - 1);
      }
    }
    res1 = res1 + !res2;
    ans[qu[j].time] = res1.answer();
  }
  for (j = 1; j <= m; j++) {
    printf("%d\n", ans[j]);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  srand(333);
  solve();
  return 0;
}

```