#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, inf = 1e9;
int func[maxn], SZ[maxn], tp[maxn], st[maxn], h[maxn], w[maxn], C, n;
vector<pair<int, int> > v[maxn];
int prep(int u, int par = 0) {
  SZ[u] = 1;
  h[u] = h[par] + 1;
  for (pair<int, int> p : v[u]) {
    if (p.first != par) SZ[u] += prep(p.first, u);
  }
  return SZ[u];
}
void build(int u, int W = inf, int par = 0, bool is = 0) {
  sort(v[u].begin(), v[u].end(), [](pair<int, int> a, pair<int, int> b) {
    return SZ[a.first] < SZ[b.first];
  });
  if (par == 0) v[u].push_back({0, 0});
  st[u] = C++;
  if (is)
    tp[u] = tp[par];
  else
    tp[u] = u;
  if (int((v[u]).size()) > 1)
    build(v[u][int((v[u]).size()) - 2].first,
          v[u][int((v[u]).size()) - 2].second, u, 1);
  for (int i = 0; i < int((v[u]).size()) - 2; i++)
    build(v[u][i].first, v[u][i].second, u, 0);
  w[st[u]] = W;
}
int a[20][maxn], sonl[20][maxn], sonr[20][maxn];
pair<int, pair<int, int> > p[20][maxn];
inline int Len(int l, int r) { return max(0, r - l); }
void buildS(int l = 0, int r = n, int h = 0) {
  if (r - l == 1) {
    a[h][l] = w[l];
    p[h][l] = {0, {1, 1}};
    return;
  }
  int mid = (l + r) >> 1;
  buildS(l, mid, h + 1);
  buildS(mid, r, h + 1);
  int pos1 = mid, pos2 = r, pos = r;
  while (l < pos) {
    if (pos2 == mid || (pos1 != l && a[h + 1][pos1 - 1] >= a[h + 1][pos2 - 1]))
      a[h][--pos] = a[h + 1][--pos1];
    else
      a[h][--pos] = a[h + 1][--pos2];
    sonl[h][pos] = pos1;
    sonr[h][pos] = pos2;
    auto p1 = p[h + 1][pos1], p2 = p[h + 1][pos2];
    if (pos1 == mid) p1 = {0, {0, 0}};
    if (pos2 == r) p2 = {0, {0, 0}};
    p[h][pos] = {p1.first + p2.first, {p1.second.first, p2.second.second}};
    bool all1 = p1.second.first == mid - l, all2 = p2.second.second == r - mid;
    if (all1) p[h][pos].second.first += p2.second.first;
    if (all2) p[h][pos].second.second += p1.second.second;
    if (!all1 && !all2)
      p[h][pos].first += func[p1.second.second + p2.second.first];
  }
}
pair<int, pair<int, int> > _Ask(int f, int s, int pos, int l = 0, int r = n,
                                int h = 0) {
  if (f >= s || l >= r || s <= l || r <= f || pos < l || r <= pos)
    return {0, {0, 0}};
  if (f <= l && r <= s) return p[h][pos];
  int mid = (l + r) >> 1;
  auto p1 = _Ask(f, s, sonl[h][pos], l, mid, h + 1),
       p2 = _Ask(f, s, sonr[h][pos], mid, r, h + 1);
  bool all1 = p1.second.first == Len(max(f, l), min(s, mid)),
       all2 = p2.second.second == Len(max(f, mid), min(s, r));
  pair<int, pair<int, int> > ans = {p1.first + p2.first,
                                    {p1.second.first, p2.second.second}};
  if (all1) ans.second.first += p2.second.first;
  if (all2) ans.second.second += p1.second.second;
  if (!all1 && !all2) ans.first += func[p1.second.second + p2.second.first];
  return ans;
}
pair<int, pair<int, int> > Ask(int f, int s, int x) {
  return _Ask(f, s, lower_bound(a[0], a[0] + n, x) - a[0]);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int q;
  cin >> n >> q;
  for (int i = 1; i <= n - 1; i++) {
    cin >> func[i];
  }
  for (int i = 1; i <= n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    v[a].push_back({b, c});
    v[b].push_back({a, c});
  }
  prep(1);
  build(1);
  buildS();
  while (q--) {
    int a, b, x;
    cin >> a >> b >> x;
    int cnta = 0, cntb = 0, ans = 0;
    while (tp[a] != tp[b]) {
      if (h[tp[a]] < h[tp[b]]) swap(a, b), swap(cnta, cntb);
      auto it = Ask(st[tp[a]], st[a] + 1, x);
      if (it.second.second == st[a] - st[tp[a]] + 1) {
        cnta += it.second.second;
      } else {
        ans += func[it.second.second + cnta] + it.first;
        cnta = it.second.first;
      }
      a = v[tp[a]].back().first;
    }
    if (h[a] < h[b]) swap(a, b), swap(cnta, cntb);
    auto it = Ask(st[b] + 1, st[a] + 1, x);
    if (it.second.second == st[a] - st[b]) {
      ans += func[cnta + cntb + it.second.second];
    } else {
      ans += func[cnta + it.second.second] + func[cntb + it.second.first] +
             it.first;
    }
    cout << ans << "\n";
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 + 10, inf = 1e9;
int func[maxn], SZ[maxn], tp[maxn], st[maxn], h[maxn], w[maxn], C, n;
vector<pair<int, int> > v[maxn];
int prep(int u, int par = 0) {
  SZ[u] = 1;
  h[u] = h[par] + 1;
  for (pair<int, int> p : v[u]) {
    if (p.first != par) SZ[u] += prep(p.first, u);
  }
  return SZ[u];
}
void build(int u, int W = inf, int par = 0, bool is = 0) {
  sort(v[u].begin(), v[u].end(), [](pair<int, int> a, pair<int, int> b) {
    return SZ[a.first] < SZ[b.first];
  });
  if (par == 0) v[u].push_back({0, 0});
  st[u] = C++;
  if (is)
    tp[u] = tp[par];
  else
    tp[u] = u;
  if (int((v[u]).size()) > 1)
    build(v[u][int((v[u]).size()) - 2].first,
          v[u][int((v[u]).size()) - 2].second, u, 1);
  for (int i = 0; i < int((v[u]).size()) - 2; i++)
    build(v[u][i].first, v[u][i].second, u, 0);
  w[st[u]] = W;
}
int a[20][maxn], sonl[20][maxn], sonr[20][maxn];
pair<int, pair<int, int> > p[20][maxn];
inline int Len(int l, int r) { return max(0, r - l); }
void buildS(int l = 0, int r = n, int h = 0) {
  if (r - l == 1) {
    a[h][l] = w[l];
    p[h][l] = {0, {1, 1}};
    return;
  }
  int mid = (l + r) >> 1;
  buildS(l, mid, h + 1);
  buildS(mid, r, h + 1);
  int pos1 = mid, pos2 = r, pos = r;
  while (l < pos) {
    if (pos2 == mid || (pos1 != l && a[h + 1][pos1 - 1] >= a[h + 1][pos2 - 1]))
      a[h][--pos] = a[h + 1][--pos1];
    else
      a[h][--pos] = a[h + 1][--pos2];
    sonl[h][pos] = pos1;
    sonr[h][pos] = pos2;
    auto p1 = p[h + 1][pos1], p2 = p[h + 1][pos2];
    if (pos1 == mid) p1 = {0, {0, 0}};
    if (pos2 == r) p2 = {0, {0, 0}};
    p[h][pos] = {p1.first + p2.first, {p1.second.first, p2.second.second}};
    bool all1 = p1.second.first == mid - l, all2 = p2.second.second == r - mid;
    if (all1) p[h][pos].second.first += p2.second.first;
    if (all2) p[h][pos].second.second += p1.second.second;
    if (!all1 && !all2)
      p[h][pos].first += func[p1.second.second + p2.second.first];
  }
}
pair<int, pair<int, int> > _Ask(int f, int s, int pos, int l = 0, int r = n,
                                int h = 0) {
  if (f >= s || l >= r || s <= l || r <= f || pos < l || r <= pos)
    return {0, {0, 0}};
  if (f <= l && r <= s) return p[h][pos];
  int mid = (l + r) >> 1;
  auto p1 = _Ask(f, s, sonl[h][pos], l, mid, h + 1),
       p2 = _Ask(f, s, sonr[h][pos], mid, r, h + 1);
  bool all1 = p1.second.first == Len(max(f, l), min(s, mid)),
       all2 = p2.second.second == Len(max(f, mid), min(s, r));
  pair<int, pair<int, int> > ans = {p1.first + p2.first,
                                    {p1.second.first, p2.second.second}};
  if (all1) ans.second.first += p2.second.first;
  if (all2) ans.second.second += p1.second.second;
  if (!all1 && !all2) ans.first += func[p1.second.second + p2.second.first];
  return ans;
}
pair<int, pair<int, int> > Ask(int f, int s, int x) {
  return _Ask(f, s, lower_bound(a[0], a[0] + n, x) - a[0]);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int q;
  cin >> n >> q;
  for (int i = 1; i <= n - 1; i++) {
    cin >> func[i];
  }
  for (int i = 1; i <= n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    v[a].push_back({b, c});
    v[b].push_back({a, c});
  }
  prep(1);
  build(1);
  buildS();
  while (q--) {
    int a, b, x;
    cin >> a >> b >> x;
    int cnta = 0, cntb = 0, ans = 0;
    while (tp[a] != tp[b]) {
      if (h[tp[a]] < h[tp[b]]) swap(a, b), swap(cnta, cntb);
      auto it = Ask(st[tp[a]], st[a] + 1, x);
      if (it.second.second == st[a] - st[tp[a]] + 1) {
        cnta += it.second.second;
      } else {
        ans += func[it.second.second + cnta] + it.first;
        cnta = it.second.first;
      }
      a = v[tp[a]].back().first;
    }
    if (h[a] < h[b]) swap(a, b), swap(cnta, cntb);
    auto it = Ask(st[b] + 1, st[a] + 1, x);
    if (it.second.second == st[a] - st[b]) {
      ans += func[cnta + cntb + it.second.second];
    } else {
      ans += func[cnta + it.second.second] + func[cntb + it.second.first] +
             it.first;
    }
    cout << ans << "\n";
  }
  return 0;
}

```