#include <bits/stdc++.h>
using namespace std;
const int LOG_N = 17;
const int N = 100500;
struct Query {
  int ind, l, r;
  Query() : ind(), l(), r() {}
  Query(int _ind, int _l, int _r) : ind(_ind), l(_l), r(_r) {}
  bool operator<(const Query& other) const {
    if (ind == other.ind) {
      if (l == other.l) return r < other.r;
      return l < other.l;
    }
    return ind < other.ind;
  }
};
int f[N];
struct Item {
  int lcnt, rcnt, sum;
  bool has_zero;
  Item() : lcnt(), rcnt(), sum(), has_zero() {}
  Item(bool one) {
    *this = Item();
    if (one)
      lcnt = rcnt = 1;
    else
      has_zero = true;
  }
  Item operator+(Item other) {
    Item res;
    res.sum = sum + other.sum;
    res.has_zero = (has_zero || other.has_zero);
    if (!has_zero && !other.has_zero)
      res.lcnt = res.rcnt = lcnt + other.lcnt;
    else if (!other.has_zero) {
      res.lcnt = lcnt;
      res.rcnt = rcnt + other.rcnt;
    } else if (!has_zero) {
      res.lcnt = lcnt + other.lcnt;
      res.rcnt = other.rcnt;
    } else {
      res.lcnt = lcnt;
      res.rcnt = other.rcnt;
      res.sum += f[rcnt + other.lcnt];
    }
    return res;
  }
  int final_sum() {
    int res = sum + f[lcnt];
    if (has_zero) res += f[rcnt];
    return res;
  }
  Item reversed() {
    Item res = *this;
    swap(res.lcnt, res.rcnt);
    return res;
  }
};
struct SegmentTree {
  vector<Item> t;
  int size;
  SegmentTree(int new_size) {
    size = 1;
    while (size < new_size) size *= 2;
    t.resize(2 * size, Item(false));
  }
  void update(int v) { t[v] = t[2 * v] + t[2 * v + 1]; }
  void set(int v) {
    v += size;
    t[v] = Item(true);
    v /= 2;
    while (v > 0) {
      update(v);
      v /= 2;
    }
  }
  Item get(int v, int l, int r, int a, int b) {
    if (a > r || b < l) return Item();
    if (a <= l && r <= b) return t[v];
    int m = (l + r) / 2;
    return get(2 * v, l, m, a, b) + get(2 * v + 1, m + 1, r, a, b);
  }
  Item get(int a, int b) { return get(1, 0, size - 1, a, b); }
};
int n, q;
vector<pair<int, int>> go[N];
int q_u[N], q_v[N], q_w[N];
int tin[N], tout[N], timer;
int par[LOG_N][N];
int par_w[N];
int size[N];
int chain_number[N];
int index_in_chain[N];
int chain_start[N];
vector<int> chain_w[N];
vector<Query> chain_queries[N];
map<int, Item> result[N];
int chains;
void dfs_init(int v, int p) {
  tin[v] = timer++;
  par[0][v] = p;
  size[v] = 1;
  for (auto e : go[v]) {
    int to = e.first;
    int w = e.second;
    if (to == p) continue;
    dfs_init(to, v);
    par_w[to] = w;
    size[v] += size[to];
  }
  tout[v] = timer++;
}
void init() {
  dfs_init(0, 0);
  for (int i = 1; i < LOG_N; i++)
    for (int v = 0; v < n; v++) par[i][v] = par[i - 1][par[i - 1][v]];
  fill(chain_number, chain_number + n, -1);
}
bool is_parent(int p, int v) { return tin[p] <= tin[v] && tout[v] <= tout[p]; }
int get_lca(int a, int b) {
  if (is_parent(a, b)) return a;
  if (is_parent(b, a)) return b;
  for (int i = LOG_N - 1; i >= 0; i--)
    if (!is_parent(par[i][a], b)) a = par[i][a];
  return par[0][a];
}
void dfs_hld(int v, int cur_chain) {
  int best = -1, best_who = -1;
  for (auto e : go[v]) {
    int to = e.first;
    if (to == par[0][v]) continue;
    if (size[to] > best) {
      best = size[to];
      best_who = to;
    }
  }
  for (auto e : go[v]) {
    int to = e.first;
    int w = e.second;
    if (to == par[0][v]) continue;
    if (to != best_who)
      dfs_hld(to, -1);
    else {
      if (cur_chain == -1) {
        cur_chain = chains++;
        chain_start[cur_chain] = to;
      }
      chain_number[to] = cur_chain;
      index_in_chain[to] = (int)chain_w[cur_chain].size();
      chain_w[cur_chain].push_back(w);
      dfs_hld(to, cur_chain);
    }
  }
}
Item hld_path(int ind, int from, int to, bool precalc) {
  if (from == to) return Item();
  int cur_chain = chain_number[from];
  if (cur_chain == -1)
    return Item(par_w[from] >= q_w[ind]) +
           hld_path(ind, par[0][from], to, precalc);
  int left = (chain_number[to] == cur_chain ? index_in_chain[to] + 1 : 0);
  int right = index_in_chain[from];
  if (precalc) {
    chain_queries[cur_chain].push_back(Query(ind, left, right));
    if (chain_number[to] != cur_chain)
      return hld_path(ind, par[0][chain_start[cur_chain]], to, precalc);
    return Item();
  }
  Item res = result[cur_chain][ind].reversed();
  if (chain_number[to] != cur_chain)
    res = res + hld_path(ind, par[0][chain_start[cur_chain]], to, precalc);
  return res;
}
int hld_query(int ind, bool precalc) {
  int a = q_u[ind];
  int b = q_v[ind];
  int c = get_lca(a, b);
  Item x = hld_path(ind, a, c, precalc);
  Item y = hld_path(ind, b, c, precalc).reversed();
  return (x + y).final_sum();
}
bool cmp_queries(const Query& a, const Query& b) {
  return q_w[a.ind] > q_w[b.ind];
}
void process_chain(int ind) {
  sort(chain_queries[ind].begin(), chain_queries[ind].end(), cmp_queries);
  SegmentTree tree((int)chain_w[ind].size());
  vector<pair<int, int>> sorted_by_w((int)chain_w[ind].size());
  for (int i = 0; i < (int)chain_w[ind].size(); i++)
    sorted_by_w[i] = make_pair(chain_w[ind][i], i);
  sort(sorted_by_w.rbegin(), sorted_by_w.rend());
  int ptr = 0;
  for (Query qu : chain_queries[ind]) {
    while (ptr < (int)sorted_by_w.size() &&
           sorted_by_w[ptr].first >= q_w[qu.ind]) {
      tree.set(sorted_by_w[ptr].second);
      ptr++;
    }
    result[ind][qu.ind] = tree.get(qu.l, qu.r);
  }
}
string slow_go_up(int from, int to, int w) {
  string path;
  while (from != to) {
    if (par_w[from] >= w)
      path += '1';
    else
      path += '0';
    from = par[0][from];
  }
  return path;
}
int slow_estimate(string s) {
  int score = 0;
  int pos = -1;
  for (int i = 0; i <= (int)s.length(); i++) {
    if (i == (int)s.length() || s[i] == '0') {
      if (pos != -1) score += f[i - pos];
      pos = -1;
    } else if (s[i] == '1' && pos == -1)
      pos = i;
  }
  return score;
}
int get_slow(int ind) {
  int a = q_u[ind];
  int b = q_v[ind];
  int w = q_w[ind];
  int c = get_lca(a, b);
  string A = slow_go_up(a, c, w);
  string B = slow_go_up(b, c, w);
  reverse(B.begin(), B.end());
  return slow_estimate(A + B);
}
void solve() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; i++) scanf("%d", &f[i]);
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    u--;
    v--;
    go[u].push_back(make_pair(v, w));
    go[v].push_back(make_pair(u, w));
  }
  init();
  dfs_hld(0, -1);
  for (int i = 0; i < q; i++) {
    scanf("%d%d%d", &q_u[i], &q_v[i], &q_w[i]);
    q_u[i]--;
    q_v[i]--;
    hld_query(i, true);
  }
  for (int i = 0; i < chains; i++) process_chain(i);
  for (int i = 0; i < q; i++) {
    int fast = hld_query(i, false);
    printf("%d\n", fast);
  }
}
int main() {
  solve();
  0;
  return 0;
}

### Prompt

Your challenge is to write 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;
const int LOG_N = 17;
const int N = 100500;
struct Query {
  int ind, l, r;
  Query() : ind(), l(), r() {}
  Query(int _ind, int _l, int _r) : ind(_ind), l(_l), r(_r) {}
  bool operator<(const Query& other) const {
    if (ind == other.ind) {
      if (l == other.l) return r < other.r;
      return l < other.l;
    }
    return ind < other.ind;
  }
};
int f[N];
struct Item {
  int lcnt, rcnt, sum;
  bool has_zero;
  Item() : lcnt(), rcnt(), sum(), has_zero() {}
  Item(bool one) {
    *this = Item();
    if (one)
      lcnt = rcnt = 1;
    else
      has_zero = true;
  }
  Item operator+(Item other) {
    Item res;
    res.sum = sum + other.sum;
    res.has_zero = (has_zero || other.has_zero);
    if (!has_zero && !other.has_zero)
      res.lcnt = res.rcnt = lcnt + other.lcnt;
    else if (!other.has_zero) {
      res.lcnt = lcnt;
      res.rcnt = rcnt + other.rcnt;
    } else if (!has_zero) {
      res.lcnt = lcnt + other.lcnt;
      res.rcnt = other.rcnt;
    } else {
      res.lcnt = lcnt;
      res.rcnt = other.rcnt;
      res.sum += f[rcnt + other.lcnt];
    }
    return res;
  }
  int final_sum() {
    int res = sum + f[lcnt];
    if (has_zero) res += f[rcnt];
    return res;
  }
  Item reversed() {
    Item res = *this;
    swap(res.lcnt, res.rcnt);
    return res;
  }
};
struct SegmentTree {
  vector<Item> t;
  int size;
  SegmentTree(int new_size) {
    size = 1;
    while (size < new_size) size *= 2;
    t.resize(2 * size, Item(false));
  }
  void update(int v) { t[v] = t[2 * v] + t[2 * v + 1]; }
  void set(int v) {
    v += size;
    t[v] = Item(true);
    v /= 2;
    while (v > 0) {
      update(v);
      v /= 2;
    }
  }
  Item get(int v, int l, int r, int a, int b) {
    if (a > r || b < l) return Item();
    if (a <= l && r <= b) return t[v];
    int m = (l + r) / 2;
    return get(2 * v, l, m, a, b) + get(2 * v + 1, m + 1, r, a, b);
  }
  Item get(int a, int b) { return get(1, 0, size - 1, a, b); }
};
int n, q;
vector<pair<int, int>> go[N];
int q_u[N], q_v[N], q_w[N];
int tin[N], tout[N], timer;
int par[LOG_N][N];
int par_w[N];
int size[N];
int chain_number[N];
int index_in_chain[N];
int chain_start[N];
vector<int> chain_w[N];
vector<Query> chain_queries[N];
map<int, Item> result[N];
int chains;
void dfs_init(int v, int p) {
  tin[v] = timer++;
  par[0][v] = p;
  size[v] = 1;
  for (auto e : go[v]) {
    int to = e.first;
    int w = e.second;
    if (to == p) continue;
    dfs_init(to, v);
    par_w[to] = w;
    size[v] += size[to];
  }
  tout[v] = timer++;
}
void init() {
  dfs_init(0, 0);
  for (int i = 1; i < LOG_N; i++)
    for (int v = 0; v < n; v++) par[i][v] = par[i - 1][par[i - 1][v]];
  fill(chain_number, chain_number + n, -1);
}
bool is_parent(int p, int v) { return tin[p] <= tin[v] && tout[v] <= tout[p]; }
int get_lca(int a, int b) {
  if (is_parent(a, b)) return a;
  if (is_parent(b, a)) return b;
  for (int i = LOG_N - 1; i >= 0; i--)
    if (!is_parent(par[i][a], b)) a = par[i][a];
  return par[0][a];
}
void dfs_hld(int v, int cur_chain) {
  int best = -1, best_who = -1;
  for (auto e : go[v]) {
    int to = e.first;
    if (to == par[0][v]) continue;
    if (size[to] > best) {
      best = size[to];
      best_who = to;
    }
  }
  for (auto e : go[v]) {
    int to = e.first;
    int w = e.second;
    if (to == par[0][v]) continue;
    if (to != best_who)
      dfs_hld(to, -1);
    else {
      if (cur_chain == -1) {
        cur_chain = chains++;
        chain_start[cur_chain] = to;
      }
      chain_number[to] = cur_chain;
      index_in_chain[to] = (int)chain_w[cur_chain].size();
      chain_w[cur_chain].push_back(w);
      dfs_hld(to, cur_chain);
    }
  }
}
Item hld_path(int ind, int from, int to, bool precalc) {
  if (from == to) return Item();
  int cur_chain = chain_number[from];
  if (cur_chain == -1)
    return Item(par_w[from] >= q_w[ind]) +
           hld_path(ind, par[0][from], to, precalc);
  int left = (chain_number[to] == cur_chain ? index_in_chain[to] + 1 : 0);
  int right = index_in_chain[from];
  if (precalc) {
    chain_queries[cur_chain].push_back(Query(ind, left, right));
    if (chain_number[to] != cur_chain)
      return hld_path(ind, par[0][chain_start[cur_chain]], to, precalc);
    return Item();
  }
  Item res = result[cur_chain][ind].reversed();
  if (chain_number[to] != cur_chain)
    res = res + hld_path(ind, par[0][chain_start[cur_chain]], to, precalc);
  return res;
}
int hld_query(int ind, bool precalc) {
  int a = q_u[ind];
  int b = q_v[ind];
  int c = get_lca(a, b);
  Item x = hld_path(ind, a, c, precalc);
  Item y = hld_path(ind, b, c, precalc).reversed();
  return (x + y).final_sum();
}
bool cmp_queries(const Query& a, const Query& b) {
  return q_w[a.ind] > q_w[b.ind];
}
void process_chain(int ind) {
  sort(chain_queries[ind].begin(), chain_queries[ind].end(), cmp_queries);
  SegmentTree tree((int)chain_w[ind].size());
  vector<pair<int, int>> sorted_by_w((int)chain_w[ind].size());
  for (int i = 0; i < (int)chain_w[ind].size(); i++)
    sorted_by_w[i] = make_pair(chain_w[ind][i], i);
  sort(sorted_by_w.rbegin(), sorted_by_w.rend());
  int ptr = 0;
  for (Query qu : chain_queries[ind]) {
    while (ptr < (int)sorted_by_w.size() &&
           sorted_by_w[ptr].first >= q_w[qu.ind]) {
      tree.set(sorted_by_w[ptr].second);
      ptr++;
    }
    result[ind][qu.ind] = tree.get(qu.l, qu.r);
  }
}
string slow_go_up(int from, int to, int w) {
  string path;
  while (from != to) {
    if (par_w[from] >= w)
      path += '1';
    else
      path += '0';
    from = par[0][from];
  }
  return path;
}
int slow_estimate(string s) {
  int score = 0;
  int pos = -1;
  for (int i = 0; i <= (int)s.length(); i++) {
    if (i == (int)s.length() || s[i] == '0') {
      if (pos != -1) score += f[i - pos];
      pos = -1;
    } else if (s[i] == '1' && pos == -1)
      pos = i;
  }
  return score;
}
int get_slow(int ind) {
  int a = q_u[ind];
  int b = q_v[ind];
  int w = q_w[ind];
  int c = get_lca(a, b);
  string A = slow_go_up(a, c, w);
  string B = slow_go_up(b, c, w);
  reverse(B.begin(), B.end());
  return slow_estimate(A + B);
}
void solve() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; i++) scanf("%d", &f[i]);
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    u--;
    v--;
    go[u].push_back(make_pair(v, w));
    go[v].push_back(make_pair(u, w));
  }
  init();
  dfs_hld(0, -1);
  for (int i = 0; i < q; i++) {
    scanf("%d%d%d", &q_u[i], &q_v[i], &q_w[i]);
    q_u[i]--;
    q_v[i]--;
    hld_query(i, true);
  }
  for (int i = 0; i < chains; i++) process_chain(i);
  for (int i = 0; i < q; i++) {
    int fast = hld_query(i, false);
    printf("%d\n", fast);
  }
}
int main() {
  solve();
  0;
  return 0;
}

```