#include <bits/stdc++.h>
using namespace std;
template <class T>
void debug(T a, T b) {
  ;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
namespace std {
template <class S, class T>
ostream& operator<<(ostream& out, const pair<S, T>& a) {
  out << '(' << a.first << ',' << a.second << ')';
  return out;
}
}  // namespace std
long long int readL() {
  long long int res;
  scanf("%I64d", &res);
  return res;
}
void printL(long long int res) { printf("%I64d", res); }
int n, q;
int prof[100005];
struct node {
  int sum;
  int L, R;
  int len;
  node() { sum = L = R = len = 0; }
  node merge(const node& a) {
    if (a.len == 0) return *this;
    if (len == 0) return a;
    node res;
    res.sum = sum + a.sum;
    if (R > 0 && a.L > 0) res.sum += prof[R + a.L] - prof[R] - prof[a.L];
    if (len != L)
      res.L = L;
    else
      res.L = len + a.L;
    if (a.len != a.R)
      res.R = a.R;
    else
      res.R = a.R + R;
    res.len = a.len + len;
    return res;
  }
  void set() {
    L = R = len = 1;
    sum = prof[1];
  }
  node flip() {
    node res = *this;
    swap(res.L, res.R);
    return res;
  }
};
struct segtree {
  vector<node> val;
  int n;
  void init(int n_) {
    n = 1;
    while (n < n_) n <<= 1;
    val.resize(n * 2);
    for (int i = 0; i < (n_); ++i) val[i + n - 1].len = 1;
    for (int i = n - 2; i >= 0; --i)
      val[i] = val[i * 2 + 1].merge(val[i * 2 + 2]);
  }
  node query(int a, int b, int i, int l, int r) {
    if (a <= l && r <= b) {
      return val[i];
    }
    if (b <= l || r <= a) return node();
    int md = (l + r) >> 1;
    node L = query(a, b, i * 2 + 1, l, md), R = query(a, b, i * 2 + 2, md, r);
    L = L.merge(R);
    return L;
  }
  void set(int k) {
    k += n - 1;
    val[k].set();
    while (k > 0) {
      k = (k - 1) / 2;
      val[k] = val[k * 2 + 1].merge(val[k * 2 + 2]);
    }
  }
};
vector<int> g[100005];
int size[100005];
pair<pair<int, int>, pair<int, int> > query[100005];
struct chain {
  vector<int> vs;
  int join;
  unordered_map<int, int> pos;
  segtree seg;
  void init(const vector<int>&, int join_);
  chain(){};
  void enable(int v) {
    int p = pos[v];
    seg.set(p);
  }
  node query(int v) { return seg.query(0, pos[v] + 1, 0, 0, seg.n); }
  node query(int l, int r) {
    return seg.query(pos[l] + 1, pos[r] + 1, 0, 0, seg.n);
  }
};
chain* belong[100005];
chain parts[100005];
void chain::init(const vector<int>& a, int join_) {
  debug((a).begin(), (a).end());
  seg.init(a.size());
  vs = a;
  join = join_;
  for (auto v : vs) belong[v] = this;
  for (int i = 0; i < (a.size()); ++i) pos[a[i]] = i;
  debug((pos).begin(), (pos).end());
  ;
  ;
}
int cnt;
int dep[100005];
int prep(int v, int p) {
  size[v] = 1;
  for (auto e : g[v]) {
    if (e == p) continue;
    dep[e] = dep[v] + 1;
    size[v] += prep(e, v);
  }
  return size[v];
}
void rec(int v, int p, vector<int>& prev, int join) {
  prev.push_back(v);
  pair<int, int> maxi = make_pair(-1, -1);
  ;
  ;
  for (auto e : g[v]) {
    if (e != p) chmax(maxi, make_pair(size[e], e));
  }
  if (maxi.first == -1) {
    parts[cnt++].init(prev, join);
    prev.clear();
  } else {
    rec(maxi.second, v, prev, join);
  }
  for (auto e : g[v]) {
    if (e != p && e != maxi.second) rec(e, v, prev, v);
  }
}
pair<int, pair<int, int> > es[100005];
int ans[100005];
int main() {
  cin >> n >> q;
  for (int i = 0; i < (n - 1); ++i) scanf("%d", &prof[i + 1]);
  for (int i = 0; i < (n - 1); ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    --u;
    --v;
    ;
    ;
    ;
    ;
    g[u].push_back(v);
    g[v].push_back(u);
    es[i] = make_pair(w, make_pair(u, v));
  }
  sort(es, es + n - 1);
  reverse(es, es + n - 1);
  for (int i = 0; i < (q); ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    --u;
    --v;
    ;
    ;
    ;
    ;
    query[i] = make_pair(make_pair(w, i), make_pair(u, v));
  };
  ;
  prep(0, -1);
  ;
  ;
  dep[n] = -114514;
  vector<int> tmpp;
  rec(0, -1, tmpp, n);
  ;
  ;
  sort(query, query + q);
  reverse(query, query + q);
  ;
  ;
  for (int i = 0; i < (n); ++i)
    ;
  ;
  int j = 0;
  for (int i = 0; i < (q); ++i) {
    pair<pair<int, int>, pair<int, int> > cur = query[i];
    int u = cur.second.first, v = cur.second.second;
    while (j < n - 1 && es[j].first >= cur.first.first) {
      int u = es[j].second.first, v = es[j].second.second;
      if (dep[u] > dep[v]) swap(u, v);
      ;
      ;
      belong[v]->enable(v);
      ++j;
    };
    ;
    ;
    ;
    ;
    ;
    node up, down;
    while (belong[u] != belong[v]) {
      ;
      ;
      ;
      ;
      if (dep[belong[u]->join] > dep[belong[v]->join]) {
        up = up.merge(belong[u]->query(u).flip());
        u = belong[u]->join;
      } else {
        down = belong[v]->query(v).merge(down);
        v = belong[v]->join;
      }
    }
    if (dep[u] < dep[v]) {
      down = belong[v]->query(u, v).merge(down);
    } else if (dep[u] > dep[v]) {
      up = up.merge(belong[u]->query(v, u).flip());
    }
    up = up.merge(down);
    ;
    ;
    ;
    ;
    ;
    ;
    ans[cur.first.second] = up.sum;
  }
  for (int i = 0; i < (q); ++i) printf("%d\n", ans[i]);
  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;
template <class T>
void debug(T a, T b) {
  ;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
namespace std {
template <class S, class T>
ostream& operator<<(ostream& out, const pair<S, T>& a) {
  out << '(' << a.first << ',' << a.second << ')';
  return out;
}
}  // namespace std
long long int readL() {
  long long int res;
  scanf("%I64d", &res);
  return res;
}
void printL(long long int res) { printf("%I64d", res); }
int n, q;
int prof[100005];
struct node {
  int sum;
  int L, R;
  int len;
  node() { sum = L = R = len = 0; }
  node merge(const node& a) {
    if (a.len == 0) return *this;
    if (len == 0) return a;
    node res;
    res.sum = sum + a.sum;
    if (R > 0 && a.L > 0) res.sum += prof[R + a.L] - prof[R] - prof[a.L];
    if (len != L)
      res.L = L;
    else
      res.L = len + a.L;
    if (a.len != a.R)
      res.R = a.R;
    else
      res.R = a.R + R;
    res.len = a.len + len;
    return res;
  }
  void set() {
    L = R = len = 1;
    sum = prof[1];
  }
  node flip() {
    node res = *this;
    swap(res.L, res.R);
    return res;
  }
};
struct segtree {
  vector<node> val;
  int n;
  void init(int n_) {
    n = 1;
    while (n < n_) n <<= 1;
    val.resize(n * 2);
    for (int i = 0; i < (n_); ++i) val[i + n - 1].len = 1;
    for (int i = n - 2; i >= 0; --i)
      val[i] = val[i * 2 + 1].merge(val[i * 2 + 2]);
  }
  node query(int a, int b, int i, int l, int r) {
    if (a <= l && r <= b) {
      return val[i];
    }
    if (b <= l || r <= a) return node();
    int md = (l + r) >> 1;
    node L = query(a, b, i * 2 + 1, l, md), R = query(a, b, i * 2 + 2, md, r);
    L = L.merge(R);
    return L;
  }
  void set(int k) {
    k += n - 1;
    val[k].set();
    while (k > 0) {
      k = (k - 1) / 2;
      val[k] = val[k * 2 + 1].merge(val[k * 2 + 2]);
    }
  }
};
vector<int> g[100005];
int size[100005];
pair<pair<int, int>, pair<int, int> > query[100005];
struct chain {
  vector<int> vs;
  int join;
  unordered_map<int, int> pos;
  segtree seg;
  void init(const vector<int>&, int join_);
  chain(){};
  void enable(int v) {
    int p = pos[v];
    seg.set(p);
  }
  node query(int v) { return seg.query(0, pos[v] + 1, 0, 0, seg.n); }
  node query(int l, int r) {
    return seg.query(pos[l] + 1, pos[r] + 1, 0, 0, seg.n);
  }
};
chain* belong[100005];
chain parts[100005];
void chain::init(const vector<int>& a, int join_) {
  debug((a).begin(), (a).end());
  seg.init(a.size());
  vs = a;
  join = join_;
  for (auto v : vs) belong[v] = this;
  for (int i = 0; i < (a.size()); ++i) pos[a[i]] = i;
  debug((pos).begin(), (pos).end());
  ;
  ;
}
int cnt;
int dep[100005];
int prep(int v, int p) {
  size[v] = 1;
  for (auto e : g[v]) {
    if (e == p) continue;
    dep[e] = dep[v] + 1;
    size[v] += prep(e, v);
  }
  return size[v];
}
void rec(int v, int p, vector<int>& prev, int join) {
  prev.push_back(v);
  pair<int, int> maxi = make_pair(-1, -1);
  ;
  ;
  for (auto e : g[v]) {
    if (e != p) chmax(maxi, make_pair(size[e], e));
  }
  if (maxi.first == -1) {
    parts[cnt++].init(prev, join);
    prev.clear();
  } else {
    rec(maxi.second, v, prev, join);
  }
  for (auto e : g[v]) {
    if (e != p && e != maxi.second) rec(e, v, prev, v);
  }
}
pair<int, pair<int, int> > es[100005];
int ans[100005];
int main() {
  cin >> n >> q;
  for (int i = 0; i < (n - 1); ++i) scanf("%d", &prof[i + 1]);
  for (int i = 0; i < (n - 1); ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    --u;
    --v;
    ;
    ;
    ;
    ;
    g[u].push_back(v);
    g[v].push_back(u);
    es[i] = make_pair(w, make_pair(u, v));
  }
  sort(es, es + n - 1);
  reverse(es, es + n - 1);
  for (int i = 0; i < (q); ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    --u;
    --v;
    ;
    ;
    ;
    ;
    query[i] = make_pair(make_pair(w, i), make_pair(u, v));
  };
  ;
  prep(0, -1);
  ;
  ;
  dep[n] = -114514;
  vector<int> tmpp;
  rec(0, -1, tmpp, n);
  ;
  ;
  sort(query, query + q);
  reverse(query, query + q);
  ;
  ;
  for (int i = 0; i < (n); ++i)
    ;
  ;
  int j = 0;
  for (int i = 0; i < (q); ++i) {
    pair<pair<int, int>, pair<int, int> > cur = query[i];
    int u = cur.second.first, v = cur.second.second;
    while (j < n - 1 && es[j].first >= cur.first.first) {
      int u = es[j].second.first, v = es[j].second.second;
      if (dep[u] > dep[v]) swap(u, v);
      ;
      ;
      belong[v]->enable(v);
      ++j;
    };
    ;
    ;
    ;
    ;
    ;
    node up, down;
    while (belong[u] != belong[v]) {
      ;
      ;
      ;
      ;
      if (dep[belong[u]->join] > dep[belong[v]->join]) {
        up = up.merge(belong[u]->query(u).flip());
        u = belong[u]->join;
      } else {
        down = belong[v]->query(v).merge(down);
        v = belong[v]->join;
      }
    }
    if (dep[u] < dep[v]) {
      down = belong[v]->query(u, v).merge(down);
    } else if (dep[u] > dep[v]) {
      up = up.merge(belong[u]->query(v, u).flip());
    }
    up = up.merge(down);
    ;
    ;
    ;
    ;
    ;
    ;
    ans[cur.first.second] = up.sum;
  }
  for (int i = 0; i < (q); ++i) printf("%d\n", ans[i]);
  return 0;
}

```