#include <bits/stdc++.h>
using namespace std;
int f[200005];
struct node {
  long long s;
  int l, r;
  bool full;
  node() {
    s = l = r = 0;
    full = 0;
  }
};
struct segment_tree {
  vector<node> st;
  segment_tree(int n) : st(4 * n) {}
  inline node combine(node l, node r) {
    node x;
    x.s = l.s + r.s + f[l.r + r.l] * (!l.full & !r.full);
    x.full = l.full & r.full;
    x.l = l.l + l.full * r.l;
    x.r = r.r + r.full * l.r;
    return x;
  }
  void update(int cur, int b, int e, int p) {
    if (b + 1 == e) {
      st[cur].l = st[cur].r = st[cur].full = 1;
      return;
    }
    int m = (b + e) >> 1;
    if (p < m)
      update(cur << 1, b, m, p);
    else
      update(cur << 1 | 1, m, e, p);
    st[cur] = combine(st[cur << 1], st[cur << 1 | 1]);
  }
  node query(int cur, int b, int e, int l, int h) {
    if (b >= l && e <= h) return st[cur];
    int m = (b + e) >> 1;
    if (l < m && m < h)
      return combine(query(cur << 1, b, m, l, h),
                     query(cur << 1 | 1, m, e, l, h));
    if (l < m) return query(cur << 1, b, m, l, h);
    return query(cur << 1 | 1, m, e, l, h);
  }
};
struct heavy_light_descomposition {
  int n;
  vector<vector<int>> G;
  vector<int> parent, depth, size, head, position;
  segment_tree st;
  heavy_light_descomposition(int n)
      : n(n),
        G(n),
        parent(n, -1),
        depth(n),
        size(n),
        head(n),
        position(n),
        st(n + 1) {}
  void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
  }
  void rootify(int r = 0) {
    vector<int> heavy(n, -1), Q(1, r);
    for (int i = 0, u; i < n; ++i) {
      size[u = Q[i]] = 1;
      for (auto v : G[u])
        if (parent[u] != v)
          Q.push_back(v), parent[v] = u, depth[v] = depth[u] + 1;
    }
    for (int i = n - 1, u; i >= 0; --i) {
      u = Q[i];
      for (auto v : G[u])
        if (parent[u] != v) {
          size[u] += size[v];
          if (heavy[u] == -1 || size[v] > size[heavy[u]]) heavy[u] = v;
        }
    }
    for (int u = 0, pos = 0; u < n; ++u)
      if (u == r || heavy[parent[u]] != u)
        for (int v = u; v != -1; v = heavy[v]) head[v] = u, position[v] = ++pos;
  }
  int lca(int u, int v) {
    while (head[u] != head[v]) {
      if (depth[head[u]] < depth[head[v]]) swap(u, v);
      u = parent[head[u]];
    }
    return (depth[u] < depth[v] ? u : v);
  }
  node query_up(int u, int v) {
    node ans;
    ans.full = 1;
    while (head[u] != head[v]) {
      ans = st.combine(
          st.query(1, 1, n + 1, position[head[u]], position[u] + 1), ans);
      u = parent[head[u]];
    }
    if (position[v] == position[u]) return ans;
    return st.combine(st.query(1, 1, n + 1, position[v] + 1, position[u] + 1),
                      ans);
  }
  long long query(int u, int v) {
    int l = lca(u, v);
    auto x = query_up(u, l), y = query_up(v, l);
    swap(x.l, x.r);
    x = st.combine(x, y);
    return x.s + f[x.l] + !x.full * f[x.r];
  }
  void update(int u) { st.update(1, 1, n + 1, position[u]); }
};
struct edge {
  int u, v, w, id;
  bool operator<(const edge &a) const { return w > a.w; }
};
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int n, m;
  cin >> n >> m;
  heavy_light_descomposition hld(n);
  for (int i = 1; i < n; ++i) cin >> f[i];
  vector<edge> e, q(m);
  for (int i = 1, u, v, w; i < n; ++i) {
    cin >> u >> v >> w;
    hld.add_edge(--u, --v);
    e.push_back({u, v, w});
  }
  int id = 0;
  for (auto &i : q) cin >> i.u >> i.v >> i.w, i.id = id++;
  hld.rootify();
  sort(e.begin(), e.end());
  sort(q.begin(), q.end());
  vector<long long> ans(m);
  for (auto i = e.begin(), k = q.begin(); k != q.end(); ++k) {
    while (i != e.end() && i->w >= k->w)
      hld.update(hld.depth[i->u] > hld.depth[i->v] ? i->u : i->v), ++i;
    ans[k->id] = hld.query(--k->u, --k->v);
  }
  for (auto &i : ans) cout << i << "\n";
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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;
int f[200005];
struct node {
  long long s;
  int l, r;
  bool full;
  node() {
    s = l = r = 0;
    full = 0;
  }
};
struct segment_tree {
  vector<node> st;
  segment_tree(int n) : st(4 * n) {}
  inline node combine(node l, node r) {
    node x;
    x.s = l.s + r.s + f[l.r + r.l] * (!l.full & !r.full);
    x.full = l.full & r.full;
    x.l = l.l + l.full * r.l;
    x.r = r.r + r.full * l.r;
    return x;
  }
  void update(int cur, int b, int e, int p) {
    if (b + 1 == e) {
      st[cur].l = st[cur].r = st[cur].full = 1;
      return;
    }
    int m = (b + e) >> 1;
    if (p < m)
      update(cur << 1, b, m, p);
    else
      update(cur << 1 | 1, m, e, p);
    st[cur] = combine(st[cur << 1], st[cur << 1 | 1]);
  }
  node query(int cur, int b, int e, int l, int h) {
    if (b >= l && e <= h) return st[cur];
    int m = (b + e) >> 1;
    if (l < m && m < h)
      return combine(query(cur << 1, b, m, l, h),
                     query(cur << 1 | 1, m, e, l, h));
    if (l < m) return query(cur << 1, b, m, l, h);
    return query(cur << 1 | 1, m, e, l, h);
  }
};
struct heavy_light_descomposition {
  int n;
  vector<vector<int>> G;
  vector<int> parent, depth, size, head, position;
  segment_tree st;
  heavy_light_descomposition(int n)
      : n(n),
        G(n),
        parent(n, -1),
        depth(n),
        size(n),
        head(n),
        position(n),
        st(n + 1) {}
  void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
  }
  void rootify(int r = 0) {
    vector<int> heavy(n, -1), Q(1, r);
    for (int i = 0, u; i < n; ++i) {
      size[u = Q[i]] = 1;
      for (auto v : G[u])
        if (parent[u] != v)
          Q.push_back(v), parent[v] = u, depth[v] = depth[u] + 1;
    }
    for (int i = n - 1, u; i >= 0; --i) {
      u = Q[i];
      for (auto v : G[u])
        if (parent[u] != v) {
          size[u] += size[v];
          if (heavy[u] == -1 || size[v] > size[heavy[u]]) heavy[u] = v;
        }
    }
    for (int u = 0, pos = 0; u < n; ++u)
      if (u == r || heavy[parent[u]] != u)
        for (int v = u; v != -1; v = heavy[v]) head[v] = u, position[v] = ++pos;
  }
  int lca(int u, int v) {
    while (head[u] != head[v]) {
      if (depth[head[u]] < depth[head[v]]) swap(u, v);
      u = parent[head[u]];
    }
    return (depth[u] < depth[v] ? u : v);
  }
  node query_up(int u, int v) {
    node ans;
    ans.full = 1;
    while (head[u] != head[v]) {
      ans = st.combine(
          st.query(1, 1, n + 1, position[head[u]], position[u] + 1), ans);
      u = parent[head[u]];
    }
    if (position[v] == position[u]) return ans;
    return st.combine(st.query(1, 1, n + 1, position[v] + 1, position[u] + 1),
                      ans);
  }
  long long query(int u, int v) {
    int l = lca(u, v);
    auto x = query_up(u, l), y = query_up(v, l);
    swap(x.l, x.r);
    x = st.combine(x, y);
    return x.s + f[x.l] + !x.full * f[x.r];
  }
  void update(int u) { st.update(1, 1, n + 1, position[u]); }
};
struct edge {
  int u, v, w, id;
  bool operator<(const edge &a) const { return w > a.w; }
};
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int n, m;
  cin >> n >> m;
  heavy_light_descomposition hld(n);
  for (int i = 1; i < n; ++i) cin >> f[i];
  vector<edge> e, q(m);
  for (int i = 1, u, v, w; i < n; ++i) {
    cin >> u >> v >> w;
    hld.add_edge(--u, --v);
    e.push_back({u, v, w});
  }
  int id = 0;
  for (auto &i : q) cin >> i.u >> i.v >> i.w, i.id = id++;
  hld.rootify();
  sort(e.begin(), e.end());
  sort(q.begin(), q.end());
  vector<long long> ans(m);
  for (auto i = e.begin(), k = q.begin(); k != q.end(); ++k) {
    while (i != e.end() && i->w >= k->w)
      hld.update(hld.depth[i->u] > hld.depth[i->v] ? i->u : i->v), ++i;
    ans[k->id] = hld.query(--k->u, --k->v);
  }
  for (auto &i : ans) cout << i << "\n";
  return 0;
}

```