#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
void ckmin(T &a, U b) {
  a = min(a, b);
}
template <class T, class U>
void ckmax(T &a, U b) {
  a = max(a, b);
}
int N, Q, T, K;
int arr[100013];
vector<pair<int, int> > edge[100013];
vector<pair<pair<int, int>, int> > quer[100013];
int ans[100013];
vector<int> compress;
int parent[100013];
int st[100013], ft[100013];
int subtree[100013], heavy[100013];
vector<int> ins[100013];
int ancestor[20][100013];
int id[100013], ranking[100013];
pair<pair<int, int>, int> comb(pair<pair<int, int>, int> a,
                               pair<pair<int, int>, int> b) {
  if (a.second == -1000000007) {
    if (b.second == -1000000007) {
      return {{a.first.first + b.first.first, a.first.first + b.first.first},
              -1000000007};
    } else {
      return {{a.first.second + b.first.first, b.first.second}, b.second};
    }
  } else {
    if (b.second == -1000000007) {
      return {{a.first.first, a.first.second + b.first.first}, a.second};
    } else {
      return {{a.first.first, b.first.second},
              a.second + b.second + arr[a.first.second + b.first.first]};
    }
  }
}
struct segtree {
  vector<pair<pair<int, int>, int> > seg;
  int n, t;
  void build(int x, int h) {
    n = x;
    t = h;
    seg.resize((1 << (33 - __builtin_clz(n))) + 2);
  }
  void update(int w, int L, int R, int a) {
    if (L == R) {
      seg[w] = {{1, 1}, -1000000007};
      return;
    }
    int mid = (L + R) >> 1;
    if (a <= mid) {
      update(w << 1, L, mid, a);
    } else {
      update(w << 1 | 1, mid + 1, R, a);
    }
    seg[w] = comb(seg[w << 1], seg[w << 1 | 1]);
  }
  pair<pair<int, int>, int> query(int w, int L, int R, int a, int b) {
    if (a <= L && R <= b) {
      return seg[w];
    }
    int mid = (L + R) >> 1;
    if (b <= mid) {
      return query(w << 1, L, mid, a, b);
    }
    if (a > mid) {
      return query(w << 1 | 1, mid + 1, R, a, b);
    }
    return comb(query(w << 1, L, mid, a, b),
                query(w << 1 | 1, mid + 1, R, a, b));
  }
};
segtree seg[100013];
void dfs(int u) {
  st[u] = T;
  ft[u] = T;
  T++;
  subtree[u] = 1;
  for (auto p : edge[u]) {
    int v = p.second;
    if (v == parent[u]) continue;
    parent[v] = u;
    dfs(v);
    ft[u] = ft[v];
    ins[p.first].push_back(v);
    subtree[u] += subtree[v];
  }
  heavy[u] = -1;
  for (auto p : edge[u]) {
    int v = p.second;
    if (v == parent[u]) continue;
    if (subtree[v] * 2 >= subtree[u]) heavy[u] = v;
  }
}
void dfs1(int u, int h, int rk) {
  for (auto p : edge[u]) {
    int v = p.second;
    if (v == parent[u]) continue;
    if (v == heavy[u]) continue;
    id[v] = K;
    K++;
    dfs1(v, v, 0);
  }
  if (heavy[u] != -1) {
    id[heavy[u]] = id[u];
    dfs1(heavy[u], h, rk + 1);
  } else {
    seg[id[u]].build(rk + 1, h);
  }
  ranking[u] = rk;
}
bool insubt(int u, int v) {
  if (u == N) return true;
  return (st[u] <= st[v] && st[v] <= ft[u]);
}
int lca(int u, int v) {
  if (insubt(v, u)) return -1;
  for (auto i = (19) - 1; i >= (0); i--) {
    if (!insubt(ancestor[i][v], u)) v = ancestor[i][v];
  }
  return v;
}
pair<pair<int, int>, int> query(int u, int v) {
  pair<pair<int, int>, int> res = {{0, 0}, -1000000007};
  while (id[u] != id[v]) {
    res = comb(seg[id[u]].query(1, 0, seg[id[u]].n - 1, 0, ranking[u]), res);
    u = parent[seg[id[u]].t];
  }
  res = comb(seg[id[u]].query(1, 0, seg[id[u]].n - 1, ranking[v], ranking[u]),
             res);
  return res;
}
void update(int u) { seg[id[u]].update(1, 0, seg[id[u]].n - 1, ranking[u]); }
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> N >> Q;
  for (auto i = (1); i < (N); i++) {
    cin >> arr[i];
  }
  for (auto i = (0); i < (N - 1); i++) {
    int u, v, d;
    cin >> u >> v >> d;
    u--;
    v--;
    compress.push_back(d);
    edge[u].push_back({d, v});
    edge[v].push_back({d, u});
  }
  sort((compress).begin(), (compress).end());
  compress.erase(unique((compress).begin(), (compress).end()), compress.end());
  for (auto i = (0); i < (N); i++) {
    for (auto &p : edge[i]) {
      p.first = lower_bound((compress).begin(), (compress).end(), p.first) -
                compress.begin();
    }
  }
  parent[0] = N;
  dfs(0);
  K = 1;
  dfs1(0, 0, 0);
  for (auto i = (0); i < (N); i++) {
    ancestor[0][i] = parent[i];
  }
  for (auto i = (0); i < (20); i++) {
    ancestor[i][N] = N;
  }
  for (auto i = (1); i < (20); i++) {
    for (auto j = (0); j < (N); j++) {
      ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
    }
  }
  for (auto i = (0); i < (Q); i++) {
    int u, v, l;
    cin >> u >> v >> l;
    u--;
    v--;
    l = lower_bound((compress).begin(), (compress).end(), l) - compress.begin();
    quer[l].push_back({{u, v}, i});
  }
  for (auto i = (N + 1) - 1; i >= (0); i--) {
    for (int x : ins[i]) {
      update(x);
    }
    for (auto p : quer[i]) {
      int u = p.first.first, v = p.first.second, qid = p.second;
      if (insubt(v, u)) swap(u, v);
      int w = lca(u, v), x = lca(v, u);
      pair<pair<int, int>, int> res;
      if (x == -1) {
        res = query(v, w);
      } else {
        pair<pair<int, int>, int> res1 = query(u, x), res2 = query(v, w);
        swap(res2.first.first, res2.first.second);
        res = comb(res2, res1);
      }
      ans[qid] =
          (res.second == -1000000007
               ? arr[res.first.first]
               : res.second + arr[res.first.first] + arr[res.first.second]);
    }
  }
  for (auto i = (0); i < (Q); i++) {
    cout << ans[i] << '\n';
  }
}

### 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;
template <class T, class U>
void ckmin(T &a, U b) {
  a = min(a, b);
}
template <class T, class U>
void ckmax(T &a, U b) {
  a = max(a, b);
}
int N, Q, T, K;
int arr[100013];
vector<pair<int, int> > edge[100013];
vector<pair<pair<int, int>, int> > quer[100013];
int ans[100013];
vector<int> compress;
int parent[100013];
int st[100013], ft[100013];
int subtree[100013], heavy[100013];
vector<int> ins[100013];
int ancestor[20][100013];
int id[100013], ranking[100013];
pair<pair<int, int>, int> comb(pair<pair<int, int>, int> a,
                               pair<pair<int, int>, int> b) {
  if (a.second == -1000000007) {
    if (b.second == -1000000007) {
      return {{a.first.first + b.first.first, a.first.first + b.first.first},
              -1000000007};
    } else {
      return {{a.first.second + b.first.first, b.first.second}, b.second};
    }
  } else {
    if (b.second == -1000000007) {
      return {{a.first.first, a.first.second + b.first.first}, a.second};
    } else {
      return {{a.first.first, b.first.second},
              a.second + b.second + arr[a.first.second + b.first.first]};
    }
  }
}
struct segtree {
  vector<pair<pair<int, int>, int> > seg;
  int n, t;
  void build(int x, int h) {
    n = x;
    t = h;
    seg.resize((1 << (33 - __builtin_clz(n))) + 2);
  }
  void update(int w, int L, int R, int a) {
    if (L == R) {
      seg[w] = {{1, 1}, -1000000007};
      return;
    }
    int mid = (L + R) >> 1;
    if (a <= mid) {
      update(w << 1, L, mid, a);
    } else {
      update(w << 1 | 1, mid + 1, R, a);
    }
    seg[w] = comb(seg[w << 1], seg[w << 1 | 1]);
  }
  pair<pair<int, int>, int> query(int w, int L, int R, int a, int b) {
    if (a <= L && R <= b) {
      return seg[w];
    }
    int mid = (L + R) >> 1;
    if (b <= mid) {
      return query(w << 1, L, mid, a, b);
    }
    if (a > mid) {
      return query(w << 1 | 1, mid + 1, R, a, b);
    }
    return comb(query(w << 1, L, mid, a, b),
                query(w << 1 | 1, mid + 1, R, a, b));
  }
};
segtree seg[100013];
void dfs(int u) {
  st[u] = T;
  ft[u] = T;
  T++;
  subtree[u] = 1;
  for (auto p : edge[u]) {
    int v = p.second;
    if (v == parent[u]) continue;
    parent[v] = u;
    dfs(v);
    ft[u] = ft[v];
    ins[p.first].push_back(v);
    subtree[u] += subtree[v];
  }
  heavy[u] = -1;
  for (auto p : edge[u]) {
    int v = p.second;
    if (v == parent[u]) continue;
    if (subtree[v] * 2 >= subtree[u]) heavy[u] = v;
  }
}
void dfs1(int u, int h, int rk) {
  for (auto p : edge[u]) {
    int v = p.second;
    if (v == parent[u]) continue;
    if (v == heavy[u]) continue;
    id[v] = K;
    K++;
    dfs1(v, v, 0);
  }
  if (heavy[u] != -1) {
    id[heavy[u]] = id[u];
    dfs1(heavy[u], h, rk + 1);
  } else {
    seg[id[u]].build(rk + 1, h);
  }
  ranking[u] = rk;
}
bool insubt(int u, int v) {
  if (u == N) return true;
  return (st[u] <= st[v] && st[v] <= ft[u]);
}
int lca(int u, int v) {
  if (insubt(v, u)) return -1;
  for (auto i = (19) - 1; i >= (0); i--) {
    if (!insubt(ancestor[i][v], u)) v = ancestor[i][v];
  }
  return v;
}
pair<pair<int, int>, int> query(int u, int v) {
  pair<pair<int, int>, int> res = {{0, 0}, -1000000007};
  while (id[u] != id[v]) {
    res = comb(seg[id[u]].query(1, 0, seg[id[u]].n - 1, 0, ranking[u]), res);
    u = parent[seg[id[u]].t];
  }
  res = comb(seg[id[u]].query(1, 0, seg[id[u]].n - 1, ranking[v], ranking[u]),
             res);
  return res;
}
void update(int u) { seg[id[u]].update(1, 0, seg[id[u]].n - 1, ranking[u]); }
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> N >> Q;
  for (auto i = (1); i < (N); i++) {
    cin >> arr[i];
  }
  for (auto i = (0); i < (N - 1); i++) {
    int u, v, d;
    cin >> u >> v >> d;
    u--;
    v--;
    compress.push_back(d);
    edge[u].push_back({d, v});
    edge[v].push_back({d, u});
  }
  sort((compress).begin(), (compress).end());
  compress.erase(unique((compress).begin(), (compress).end()), compress.end());
  for (auto i = (0); i < (N); i++) {
    for (auto &p : edge[i]) {
      p.first = lower_bound((compress).begin(), (compress).end(), p.first) -
                compress.begin();
    }
  }
  parent[0] = N;
  dfs(0);
  K = 1;
  dfs1(0, 0, 0);
  for (auto i = (0); i < (N); i++) {
    ancestor[0][i] = parent[i];
  }
  for (auto i = (0); i < (20); i++) {
    ancestor[i][N] = N;
  }
  for (auto i = (1); i < (20); i++) {
    for (auto j = (0); j < (N); j++) {
      ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
    }
  }
  for (auto i = (0); i < (Q); i++) {
    int u, v, l;
    cin >> u >> v >> l;
    u--;
    v--;
    l = lower_bound((compress).begin(), (compress).end(), l) - compress.begin();
    quer[l].push_back({{u, v}, i});
  }
  for (auto i = (N + 1) - 1; i >= (0); i--) {
    for (int x : ins[i]) {
      update(x);
    }
    for (auto p : quer[i]) {
      int u = p.first.first, v = p.first.second, qid = p.second;
      if (insubt(v, u)) swap(u, v);
      int w = lca(u, v), x = lca(v, u);
      pair<pair<int, int>, int> res;
      if (x == -1) {
        res = query(v, w);
      } else {
        pair<pair<int, int>, int> res1 = query(u, x), res2 = query(v, w);
        swap(res2.first.first, res2.first.second);
        res = comb(res2, res1);
      }
      ans[qid] =
          (res.second == -1000000007
               ? arr[res.first.first]
               : res.second + arr[res.first.first] + arr[res.first.second]);
    }
  }
  for (auto i = (0); i < (Q); i++) {
    cout << ans[i] << '\n';
  }
}

```