#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using db = long double;
using ii = pair<int, int>;
const int N = 1e5 + 5, LG = 17, MOD = 998244353;
const int SQ = 225;
const long double EPS = 1e-7;
int n, q, f[N], lvl[N], par[N];
vector<ii> edges;
struct Nd {
  bool all;
  int prefix, suffix, sum;
  Nd(int x = 0) {
    all = prefix = suffix = x;
    sum = 0;
  }
  int calc() {
    if (all) return f[prefix];
    return sum + f[prefix] + f[suffix];
  }
} t[N << 2];
Nd flip(Nd x) {
  swap(x.prefix, x.suffix);
  return x;
}
Nd operator+(Nd a, Nd b) {
  Nd ret;
  ret.all = a.all & b.all;
  ret.prefix = a.prefix + a.all * b.prefix;
  ret.suffix = b.suffix + b.all * a.suffix;
  ret.sum = a.sum + b.sum + (!b.all) * (!a.all) * f[a.suffix + b.prefix];
  return ret;
}
void upd(int node, int s, int e, int idx) {
  if (s == e) {
    t[node] = Nd(1);
  } else {
    int md = (s + e) >> 1;
    if (idx <= md)
      upd(node << 1, s, md, idx);
    else
      upd(node << 1 | 1, md + 1, e, idx);
    t[node] = t[node << 1] + t[node << 1 | 1];
  }
}
Nd qry(int node, int s, int e, int l, int r) {
  if (r < s || e < l) {
    Nd ret;
    ret.all = true;
    return ret;
  }
  if (l <= s && e <= r) return t[node];
  int md = (s + e) >> 1;
  return qry(node << 1, s, md, l, r) + qry(node << 1 | 1, md + 1, e, l, r);
}
vector<ii> adj[N];
int sz[N], pos[N], head[N], ptr;
void pDFS(int node, int p) {
  sz[node] = 1;
  for (auto& x : adj[node]) {
    if (x.first == p) swap(x, adj[node].back());
    if (x.first == p) continue;
    edges.push_back({x.second, x.first});
    lvl[x.first] = lvl[node] + 1;
    par[x.first] = node;
    pDFS(x.first, node);
    sz[node] += sz[x.first];
    if (sz[x.first] > sz[adj[node][0].first]) swap(x, adj[node][0]);
  }
  if (node != 1) adj[node].pop_back();
}
void hDFS(int node) {
  pos[node] = ptr++;
  for (auto x : adj[node]) {
    if (x == adj[node][0])
      head[x.first] = head[node];
    else
      head[x.first] = x.first;
    hDFS(x.first);
  }
}
Nd query(int u, int v) {
  if (head[u] == head[v]) {
    if (lvl[u] < lvl[v]) return qry(1, 0, n - 1, pos[u] + 1, pos[v]);
    return flip(qry(1, 0, n - 1, pos[v] + 1, pos[u]));
  } else {
    if (lvl[head[u]] < lvl[head[v]])
      return query(u, par[head[v]]) + qry(1, 0, n - 1, pos[head[v]], pos[v]);
    return flip(query(v, par[head[u]]) +
                qry(1, 0, n - 1, pos[head[u]], pos[u]));
  }
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i < n; i++) cin >> f[i];
  for (int i = 1; i < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back(ii(v, w));
    adj[v].push_back(ii(u, w));
  }
  pDFS(1, 1);
  head[1] = 1;
  hDFS(1);
  vector<vector<int>> queries;
  for (int i = 0; i < q; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    queries.push_back({w, u, v, i});
  }
  sort(queries.rbegin(), queries.rend());
  sort(edges.rbegin(), edges.rend());
  vector<int> ans(q);
  for (int i = 0, j = 0; i < queries.size(); i++) {
    for (; j < edges.size() && edges[j].first >= queries[i][0]; j++) {
      upd(1, 0, n - 1, pos[edges[j].second]);
    }
    ans[queries[i].back()] = query(queries[i][1], queries[i][2]).calc();
  }
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
  return 0;
}

### Prompt

Your task is to create 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>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using db = long double;
using ii = pair<int, int>;
const int N = 1e5 + 5, LG = 17, MOD = 998244353;
const int SQ = 225;
const long double EPS = 1e-7;
int n, q, f[N], lvl[N], par[N];
vector<ii> edges;
struct Nd {
  bool all;
  int prefix, suffix, sum;
  Nd(int x = 0) {
    all = prefix = suffix = x;
    sum = 0;
  }
  int calc() {
    if (all) return f[prefix];
    return sum + f[prefix] + f[suffix];
  }
} t[N << 2];
Nd flip(Nd x) {
  swap(x.prefix, x.suffix);
  return x;
}
Nd operator+(Nd a, Nd b) {
  Nd ret;
  ret.all = a.all & b.all;
  ret.prefix = a.prefix + a.all * b.prefix;
  ret.suffix = b.suffix + b.all * a.suffix;
  ret.sum = a.sum + b.sum + (!b.all) * (!a.all) * f[a.suffix + b.prefix];
  return ret;
}
void upd(int node, int s, int e, int idx) {
  if (s == e) {
    t[node] = Nd(1);
  } else {
    int md = (s + e) >> 1;
    if (idx <= md)
      upd(node << 1, s, md, idx);
    else
      upd(node << 1 | 1, md + 1, e, idx);
    t[node] = t[node << 1] + t[node << 1 | 1];
  }
}
Nd qry(int node, int s, int e, int l, int r) {
  if (r < s || e < l) {
    Nd ret;
    ret.all = true;
    return ret;
  }
  if (l <= s && e <= r) return t[node];
  int md = (s + e) >> 1;
  return qry(node << 1, s, md, l, r) + qry(node << 1 | 1, md + 1, e, l, r);
}
vector<ii> adj[N];
int sz[N], pos[N], head[N], ptr;
void pDFS(int node, int p) {
  sz[node] = 1;
  for (auto& x : adj[node]) {
    if (x.first == p) swap(x, adj[node].back());
    if (x.first == p) continue;
    edges.push_back({x.second, x.first});
    lvl[x.first] = lvl[node] + 1;
    par[x.first] = node;
    pDFS(x.first, node);
    sz[node] += sz[x.first];
    if (sz[x.first] > sz[adj[node][0].first]) swap(x, adj[node][0]);
  }
  if (node != 1) adj[node].pop_back();
}
void hDFS(int node) {
  pos[node] = ptr++;
  for (auto x : adj[node]) {
    if (x == adj[node][0])
      head[x.first] = head[node];
    else
      head[x.first] = x.first;
    hDFS(x.first);
  }
}
Nd query(int u, int v) {
  if (head[u] == head[v]) {
    if (lvl[u] < lvl[v]) return qry(1, 0, n - 1, pos[u] + 1, pos[v]);
    return flip(qry(1, 0, n - 1, pos[v] + 1, pos[u]));
  } else {
    if (lvl[head[u]] < lvl[head[v]])
      return query(u, par[head[v]]) + qry(1, 0, n - 1, pos[head[v]], pos[v]);
    return flip(query(v, par[head[u]]) +
                qry(1, 0, n - 1, pos[head[u]], pos[u]));
  }
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i < n; i++) cin >> f[i];
  for (int i = 1; i < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back(ii(v, w));
    adj[v].push_back(ii(u, w));
  }
  pDFS(1, 1);
  head[1] = 1;
  hDFS(1);
  vector<vector<int>> queries;
  for (int i = 0; i < q; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    queries.push_back({w, u, v, i});
  }
  sort(queries.rbegin(), queries.rend());
  sort(edges.rbegin(), edges.rend());
  vector<int> ans(q);
  for (int i = 0, j = 0; i < queries.size(); i++) {
    for (; j < edges.size() && edges[j].first >= queries[i][0]; j++) {
      upd(1, 0, n - 1, pos[edges[j].second]);
    }
    ans[queries[i].back()] = query(queries[i][1], queries[i][2]).calc();
  }
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
  return 0;
}

```