#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void umax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void umin(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <class T>
inline T gcd(T a, T b) {
  return __gcd(a, b);
}
template <class T>
inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
const int inf = 1e9 + 143;
const long long llonginf = 1e18 + 143;
inline int read() {
  int x;
  scanf(" %d", &x);
  return x;
}
const int N = 1 << 17;
const int LOG = 18;
int f[N];
int ans[N];
int d[N], par[N];
int anc[N][LOG];
int sz[N];
vector<pair<int, pair<int, int> > > es;
vector<pair<pair<int, int>, pair<int, int> > > qs;
vector<int> g[N];
int id[N], hptr = 0;
int up[N];
struct node {
  int lval, rval, sum, sz;
  node() { lval = rval = sum = sz = 0; }
  node(int _lval, int _rval, int _sum, int _sz) {
    lval = _lval;
    rval = _rval;
    sum = _sum;
    sz = _sz;
  }
  friend node operator+(const node &a, const node &b) {
    if (a.sz == 0) return b;
    if (b.sz == 0) return a;
    node res;
    res.sz = a.sz + b.sz;
    bool afull = (a.sz == a.lval);
    bool bfull = (b.sz == b.lval);
    res.sum = a.sum + b.sum;
    res.lval = afull ? a.sz + b.lval : a.lval;
    res.rval = bfull ? b.sz + a.rval : b.rval;
    if (!afull && !bfull) res.sum += f[a.rval + b.lval];
    return res;
  }
  node flip() {
    node res = *this;
    swap(res.lval, res.rval);
    return res;
  }
  int act() {
    if (sz == lval) return f[sz];
    return sum + f[lval] + f[rval];
  }
};
node T[N << 1];
void init() {
  for (int i = 0; i < N; i++) T[i + N].sz = 1;
  for (int i = N - 1; i > 0; i--) T[i] = T[i + i] + T[i + i + 1];
}
void tadd(int x) {
  x += N;
  T[x] = node(1, 1, 0, 1);
  while (x > 1) {
    x >>= 1;
    T[x] = T[x + x] + T[x + x + 1];
  }
}
node get(int x, int l, int r, int x1, int x2) {
  if (l > x2 || r < x1) return node();
  if (l >= x1 && r <= x2) return T[x];
  int m = (l + r) >> 1;
  return get(x + x, l, m, x1, x2) + get(x + x + 1, m + 1, r, x1, x2);
}
void dfs(int u, int p) {
  anc[u][0] = p;
  for (int i = 1; i < LOG; i++) {
    anc[u][i] = anc[anc[u][i - 1]][i - 1];
  }
  sz[u] = 1;
  for (__typeof((g[u]).begin()) it = (g[u]).begin(); it != (g[u]).end(); it++) {
    int v = *it;
    if (v != p) {
      par[v] = u;
      d[v] = d[u] + 1;
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}
inline int jump(int u, int d) {
  for (int i = 0; i < LOG; i++) {
    if (d & (1 << i)) u = anc[u][i];
  }
  return u;
}
int get_lca(int a, int b) {
  if (d[a] < d[b]) swap(a, b);
  a = jump(a, d[a] - d[b]);
  if (a == b) return a;
  for (int i = LOG - 1; i >= 0; i--) {
    if (anc[a][i] != anc[b][i]) {
      a = anc[a][i];
      b = anc[b][i];
    }
  }
  return anc[a][0];
}
void build(int u, int p) {
  id[u] = ++hptr;
  int mxid = -1;
  for (__typeof((g[u]).begin()) it = (g[u]).begin(); it != (g[u]).end(); it++) {
    int v = *it;
    if (v != p && (mxid == -1 || sz[mxid] < sz[v])) {
      mxid = v;
    }
  }
  if (mxid != -1) {
    up[mxid] = up[u] ? up[u] : u;
    build(mxid, u);
  }
  for (__typeof((g[u]).begin()) it = (g[u]).begin(); it != (g[u]).end(); it++) {
    int v = *it;
    if (v != p && v != mxid) {
      up[v] = 0;
      build(v, u);
    }
  }
}
bool on[N];
void add(int u, int p) {
  if (par[p] == u) swap(u, p);
  assert(par[u] == p);
  on[u] = true;
  tadd(id[u]);
}
node get_path(int u, int to) {
  node res;
  while (d[u] > d[to]) {
    if (up[u]) {
      int next = up[u];
      if (d[next] < d[to]) {
        next = to;
      }
      res = get(1, 0, N - 1, id[next] + 1, id[u]) + res;
      u = next;
    } else {
      res = get(1, 0, N - 1, id[u], id[u]) + res;
      u = par[u];
    }
  }
  return res;
}
node query(int u, int v) {
  int lca = get_lca(u, v);
  if (v == lca) {
    swap(u, v);
  }
  if (u == lca) {
    return get_path(v, lca);
  } else {
    return get_path(v, lca).flip() + get_path(u, lca);
  }
}
int main() {
  int n = read();
  int q = read();
  f[0] = 0;
  for (int i = 1; i < n; i++) {
    f[i] = read();
  }
  for (int i = 1; i < n; i++) {
    int a = read();
    int b = read();
    int c = read();
    g[a].push_back(b);
    g[b].push_back(a);
    es.push_back(make_pair(c, pair<int, int>(a, b)));
  }
  dfs(1, 0);
  build(1, 0);
  for (int i = 0; i < q; i++) {
    int a = read();
    int b = read();
    int c = read();
    qs.push_back(make_pair(pair<int, int>(c, i), pair<int, int>(a, b)));
  }
  sort((es).begin(), (es).end());
  reverse((es).begin(), (es).end());
  sort((qs).begin(), (qs).end());
  reverse((qs).begin(), (qs).end());
  init();
  int ptr = 0;
  for (int i = 0; i < qs.size(); i++) {
    int L = qs[i].first.first;
    int id = qs[i].first.second;
    int u = qs[i].second.first;
    int v = qs[i].second.second;
    while (ptr < es.size() && es[ptr].first >= L) {
      add(es[ptr].second.first, es[ptr].second.second);
      ptr++;
    }
    ans[id] = query(u, v).act();
  }
  for (int i = 0; i < q; i++) {
    printf("%d\n", ans[i]);
  }
  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;
template <class T>
inline void umax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void umin(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <class T>
inline T gcd(T a, T b) {
  return __gcd(a, b);
}
template <class T>
inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
const int inf = 1e9 + 143;
const long long llonginf = 1e18 + 143;
inline int read() {
  int x;
  scanf(" %d", &x);
  return x;
}
const int N = 1 << 17;
const int LOG = 18;
int f[N];
int ans[N];
int d[N], par[N];
int anc[N][LOG];
int sz[N];
vector<pair<int, pair<int, int> > > es;
vector<pair<pair<int, int>, pair<int, int> > > qs;
vector<int> g[N];
int id[N], hptr = 0;
int up[N];
struct node {
  int lval, rval, sum, sz;
  node() { lval = rval = sum = sz = 0; }
  node(int _lval, int _rval, int _sum, int _sz) {
    lval = _lval;
    rval = _rval;
    sum = _sum;
    sz = _sz;
  }
  friend node operator+(const node &a, const node &b) {
    if (a.sz == 0) return b;
    if (b.sz == 0) return a;
    node res;
    res.sz = a.sz + b.sz;
    bool afull = (a.sz == a.lval);
    bool bfull = (b.sz == b.lval);
    res.sum = a.sum + b.sum;
    res.lval = afull ? a.sz + b.lval : a.lval;
    res.rval = bfull ? b.sz + a.rval : b.rval;
    if (!afull && !bfull) res.sum += f[a.rval + b.lval];
    return res;
  }
  node flip() {
    node res = *this;
    swap(res.lval, res.rval);
    return res;
  }
  int act() {
    if (sz == lval) return f[sz];
    return sum + f[lval] + f[rval];
  }
};
node T[N << 1];
void init() {
  for (int i = 0; i < N; i++) T[i + N].sz = 1;
  for (int i = N - 1; i > 0; i--) T[i] = T[i + i] + T[i + i + 1];
}
void tadd(int x) {
  x += N;
  T[x] = node(1, 1, 0, 1);
  while (x > 1) {
    x >>= 1;
    T[x] = T[x + x] + T[x + x + 1];
  }
}
node get(int x, int l, int r, int x1, int x2) {
  if (l > x2 || r < x1) return node();
  if (l >= x1 && r <= x2) return T[x];
  int m = (l + r) >> 1;
  return get(x + x, l, m, x1, x2) + get(x + x + 1, m + 1, r, x1, x2);
}
void dfs(int u, int p) {
  anc[u][0] = p;
  for (int i = 1; i < LOG; i++) {
    anc[u][i] = anc[anc[u][i - 1]][i - 1];
  }
  sz[u] = 1;
  for (__typeof((g[u]).begin()) it = (g[u]).begin(); it != (g[u]).end(); it++) {
    int v = *it;
    if (v != p) {
      par[v] = u;
      d[v] = d[u] + 1;
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}
inline int jump(int u, int d) {
  for (int i = 0; i < LOG; i++) {
    if (d & (1 << i)) u = anc[u][i];
  }
  return u;
}
int get_lca(int a, int b) {
  if (d[a] < d[b]) swap(a, b);
  a = jump(a, d[a] - d[b]);
  if (a == b) return a;
  for (int i = LOG - 1; i >= 0; i--) {
    if (anc[a][i] != anc[b][i]) {
      a = anc[a][i];
      b = anc[b][i];
    }
  }
  return anc[a][0];
}
void build(int u, int p) {
  id[u] = ++hptr;
  int mxid = -1;
  for (__typeof((g[u]).begin()) it = (g[u]).begin(); it != (g[u]).end(); it++) {
    int v = *it;
    if (v != p && (mxid == -1 || sz[mxid] < sz[v])) {
      mxid = v;
    }
  }
  if (mxid != -1) {
    up[mxid] = up[u] ? up[u] : u;
    build(mxid, u);
  }
  for (__typeof((g[u]).begin()) it = (g[u]).begin(); it != (g[u]).end(); it++) {
    int v = *it;
    if (v != p && v != mxid) {
      up[v] = 0;
      build(v, u);
    }
  }
}
bool on[N];
void add(int u, int p) {
  if (par[p] == u) swap(u, p);
  assert(par[u] == p);
  on[u] = true;
  tadd(id[u]);
}
node get_path(int u, int to) {
  node res;
  while (d[u] > d[to]) {
    if (up[u]) {
      int next = up[u];
      if (d[next] < d[to]) {
        next = to;
      }
      res = get(1, 0, N - 1, id[next] + 1, id[u]) + res;
      u = next;
    } else {
      res = get(1, 0, N - 1, id[u], id[u]) + res;
      u = par[u];
    }
  }
  return res;
}
node query(int u, int v) {
  int lca = get_lca(u, v);
  if (v == lca) {
    swap(u, v);
  }
  if (u == lca) {
    return get_path(v, lca);
  } else {
    return get_path(v, lca).flip() + get_path(u, lca);
  }
}
int main() {
  int n = read();
  int q = read();
  f[0] = 0;
  for (int i = 1; i < n; i++) {
    f[i] = read();
  }
  for (int i = 1; i < n; i++) {
    int a = read();
    int b = read();
    int c = read();
    g[a].push_back(b);
    g[b].push_back(a);
    es.push_back(make_pair(c, pair<int, int>(a, b)));
  }
  dfs(1, 0);
  build(1, 0);
  for (int i = 0; i < q; i++) {
    int a = read();
    int b = read();
    int c = read();
    qs.push_back(make_pair(pair<int, int>(c, i), pair<int, int>(a, b)));
  }
  sort((es).begin(), (es).end());
  reverse((es).begin(), (es).end());
  sort((qs).begin(), (qs).end());
  reverse((qs).begin(), (qs).end());
  init();
  int ptr = 0;
  for (int i = 0; i < qs.size(); i++) {
    int L = qs[i].first.first;
    int id = qs[i].first.second;
    int u = qs[i].second.first;
    int v = qs[i].second.second;
    while (ptr < es.size() && es[ptr].first >= L) {
      add(es[ptr].second.first, es[ptr].second.second);
      ptr++;
    }
    ans[id] = query(u, v).act();
  }
  for (int i = 0; i < q; i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}

```