#include <bits/stdc++.h>
using namespace std;
clock_t __stt;
inline void TStart() { __stt = clock(); }
inline void TReport() {
  printf("\nTaken Time : %.3lf sec\n",
         (double)(clock() - __stt) / CLOCKS_PER_SEC);
}
template <typename T>
T MIN(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
T MAX(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
T ABS(T a) {
  return a > 0 ? a : (-a);
}
template <typename T>
void UMIN(T &a, T b) {
  if (b < a) a = b;
}
template <typename T>
void UMAX(T &a, T b) {
  if (b > a) a = b;
}
int n, q, f[100005];
vector<int> adj[100005];
struct data {
  int L, R, cost;
  bool pure;
  void set(int _L, int _R, int _cost, bool _pure) {
    L = _L;
    R = _R;
    cost = _cost;
    pure = _pure;
  }
  void init0() { set(0, 0, 0, 0); }
  void init1() { set(1, 1, f[1], 1); }
};
data merge(data A, data B) {
  data ret;
  if (A.L == -1) return B;
  if (B.L == -1) return A;
  if (A.pure)
    ret.set(A.L + B.L, B.R + (B.pure ? A.R : 0), B.cost - f[B.L] + f[A.R + B.L],
            B.pure);
  else if (B.pure)
    ret.set(A.L, A.R + B.R, A.cost - f[A.R] + f[A.R + B.R], 0);
  else
    ret.set(A.L, B.R, A.cost + B.cost - f[A.R] - f[B.L] + f[A.R + B.L], 0);
  return ret;
}
data rev(data A) {
  swap(A.L, A.R);
  return A;
}
namespace segT {
data arr[400005];
void init(int p, int l = 0, int r = n - 1) {
  arr[p].init0();
  if (l < r) {
    int M = (l + r) / 2;
    init(p << 1, l, M);
    init(p << 1 | 1, M + 1, r);
  }
}
void set1(int p, int d, int l = 0, int r = n - 1) {
  if (l == r) {
    arr[p].init1();
    return;
  }
  int M = (l + r) / 2;
  if (d <= M)
    set1(p << 1, d, l, M);
  else
    set1(p << 1 | 1, d, M + 1, r);
  arr[p] = merge(arr[p << 1 | 1], arr[p << 1]);
}
data query(int p, int L, int R, int l = 0, int r = n - 1) {
  if (l >= L && r <= R) return arr[p];
  int M = (l + r) / 2;
  data ret;
  ret.set(-1, -1, 0, 0);
  if (L <= M) ret = query(p << 1, L, R, l, M);
  if (R > M) ret = merge(query(p << 1 | 1, L, R, M + 1, r), ret);
  return ret;
}
};  // namespace segT
namespace HLD {
int sz[100005], mxson[100005], tpver[100005], cid[100005], tick;
int fa[20][100005], dep[100005];
void pdfs(int v, int f) {
  int i;
  sz[v] = 1;
  fa[0][v] = f;
  dep[v] = (f == -1 ? 0 : dep[f] + 1);
  mxson[v] = -1;
  for (i = 0; i < (int)adj[v].size(); ++i) {
    int u = adj[v][i];
    if (u != f) {
      pdfs(u, v);
      sz[v] += sz[u];
      if (mxson[v] == -1 || sz[u] > sz[mxson[v]]) mxson[v] = u;
    }
  }
}
void precal() {
  int i, j, k;
  for (i = 1; i < 20; ++i) {
    for (j = 0; j < n; ++j) {
      if (fa[i - 1][j] == -1)
        fa[i][j] = -1;
      else
        fa[i][j] = fa[i - 1][fa[i - 1][j]];
    }
  }
}
int lca(int u, int v) {
  int i;
  if (dep[u] < dep[v]) swap(u, v);
  for (i = 19; i >= 0; --i) {
    if (fa[i][u] != -1 && dep[fa[i][u]] >= dep[v]) u = fa[i][u];
  }
  if (u == v) return u;
  for (i = 19; i >= 0; --i) {
    if (fa[i][u] != fa[i][v]) {
      u = fa[i][u];
      v = fa[i][v];
    }
  }
  return fa[0][u];
}
int jump(int u, int d) {
  int i;
  if (d < 0) return -1;
  for (i = 0; i < 20; ++i, d >>= 1) {
    if (d & 1) u = fa[i][u];
  }
  return u;
}
void build(int v, int tpv) {
  int i;
  cid[v] = tick++;
  tpver[v] = tpv;
  if (mxson[v] != -1) build(mxson[v], tpv);
  for (i = 0; i < (int)adj[v].size(); ++i) {
    int u = adj[v][i];
    if (u != fa[0][v] && u != mxson[v]) {
      build(u, u);
    }
  }
}
data query(int u, int v) {
  int i, j, k;
  data ret;
  ret.set(-1, -1, 0, 0);
  if (u == -1 || v == -1) return ret;
  while (tpver[u] != tpver[v]) {
    ret = merge(ret, segT::query(1, cid[tpver[u]], cid[u]));
    u = fa[0][tpver[u]];
  }
  ret = merge(ret, segT::query(1, cid[v], cid[u]));
  return ret;
}
data queryfull(int u, int v) {
  int f = lca(u, v);
  int fv = jump(v, dep[v] - dep[f] - 1), fu = jump(u, dep[u] - dep[f] - 1);
  return merge(query(u, fu), rev(query(v, fv)));
}
void set1(int v) { segT::set1(1, cid[v]); }
};  // namespace HLD
pair<int, pair<int, int> > eds[100005];
int res[100005], u[100005], v[100005];
pair<int, int> qs[100005];
int main() {
  int i, j, k;
  scanf("%d%d", &n, &q);
  for (i = 1; i < n; ++i) scanf("%d", f + i);
  for (i = 0; i < n - 1; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    --u;
    --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
    eds[i] = make_pair(w, make_pair(u, v));
  }
  for (i = 0; i < q; ++i) {
    scanf("%d%d%d", u + i, v + i, &k);
    --u[i];
    --v[i];
    qs[i] = make_pair(k, i);
  }
  sort(eds, eds + n - 1);
  sort(qs, qs + q);
  segT::init(1);
  HLD::tick = 0;
  HLD::pdfs(0, -1);
  HLD::build(0, 0);
  HLD::precal();
  int ptr = n - 2;
  for (i = q - 1; i >= 0; --i) {
    int id = qs[i].second, w = qs[i].first;
    while (ptr >= 0 && eds[ptr].first >= w) {
      int u = eds[ptr].second.first, v = eds[ptr].second.second;
      HLD::set1(HLD::dep[u] < HLD::dep[v] ? v : u);
      --ptr;
    }
    res[id] = HLD::queryfull(u[id], v[id]).cost;
  }
  for (i = 0; i < q; ++i) printf("%d\n", res[i]);
  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>
using namespace std;
clock_t __stt;
inline void TStart() { __stt = clock(); }
inline void TReport() {
  printf("\nTaken Time : %.3lf sec\n",
         (double)(clock() - __stt) / CLOCKS_PER_SEC);
}
template <typename T>
T MIN(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
T MAX(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
T ABS(T a) {
  return a > 0 ? a : (-a);
}
template <typename T>
void UMIN(T &a, T b) {
  if (b < a) a = b;
}
template <typename T>
void UMAX(T &a, T b) {
  if (b > a) a = b;
}
int n, q, f[100005];
vector<int> adj[100005];
struct data {
  int L, R, cost;
  bool pure;
  void set(int _L, int _R, int _cost, bool _pure) {
    L = _L;
    R = _R;
    cost = _cost;
    pure = _pure;
  }
  void init0() { set(0, 0, 0, 0); }
  void init1() { set(1, 1, f[1], 1); }
};
data merge(data A, data B) {
  data ret;
  if (A.L == -1) return B;
  if (B.L == -1) return A;
  if (A.pure)
    ret.set(A.L + B.L, B.R + (B.pure ? A.R : 0), B.cost - f[B.L] + f[A.R + B.L],
            B.pure);
  else if (B.pure)
    ret.set(A.L, A.R + B.R, A.cost - f[A.R] + f[A.R + B.R], 0);
  else
    ret.set(A.L, B.R, A.cost + B.cost - f[A.R] - f[B.L] + f[A.R + B.L], 0);
  return ret;
}
data rev(data A) {
  swap(A.L, A.R);
  return A;
}
namespace segT {
data arr[400005];
void init(int p, int l = 0, int r = n - 1) {
  arr[p].init0();
  if (l < r) {
    int M = (l + r) / 2;
    init(p << 1, l, M);
    init(p << 1 | 1, M + 1, r);
  }
}
void set1(int p, int d, int l = 0, int r = n - 1) {
  if (l == r) {
    arr[p].init1();
    return;
  }
  int M = (l + r) / 2;
  if (d <= M)
    set1(p << 1, d, l, M);
  else
    set1(p << 1 | 1, d, M + 1, r);
  arr[p] = merge(arr[p << 1 | 1], arr[p << 1]);
}
data query(int p, int L, int R, int l = 0, int r = n - 1) {
  if (l >= L && r <= R) return arr[p];
  int M = (l + r) / 2;
  data ret;
  ret.set(-1, -1, 0, 0);
  if (L <= M) ret = query(p << 1, L, R, l, M);
  if (R > M) ret = merge(query(p << 1 | 1, L, R, M + 1, r), ret);
  return ret;
}
};  // namespace segT
namespace HLD {
int sz[100005], mxson[100005], tpver[100005], cid[100005], tick;
int fa[20][100005], dep[100005];
void pdfs(int v, int f) {
  int i;
  sz[v] = 1;
  fa[0][v] = f;
  dep[v] = (f == -1 ? 0 : dep[f] + 1);
  mxson[v] = -1;
  for (i = 0; i < (int)adj[v].size(); ++i) {
    int u = adj[v][i];
    if (u != f) {
      pdfs(u, v);
      sz[v] += sz[u];
      if (mxson[v] == -1 || sz[u] > sz[mxson[v]]) mxson[v] = u;
    }
  }
}
void precal() {
  int i, j, k;
  for (i = 1; i < 20; ++i) {
    for (j = 0; j < n; ++j) {
      if (fa[i - 1][j] == -1)
        fa[i][j] = -1;
      else
        fa[i][j] = fa[i - 1][fa[i - 1][j]];
    }
  }
}
int lca(int u, int v) {
  int i;
  if (dep[u] < dep[v]) swap(u, v);
  for (i = 19; i >= 0; --i) {
    if (fa[i][u] != -1 && dep[fa[i][u]] >= dep[v]) u = fa[i][u];
  }
  if (u == v) return u;
  for (i = 19; i >= 0; --i) {
    if (fa[i][u] != fa[i][v]) {
      u = fa[i][u];
      v = fa[i][v];
    }
  }
  return fa[0][u];
}
int jump(int u, int d) {
  int i;
  if (d < 0) return -1;
  for (i = 0; i < 20; ++i, d >>= 1) {
    if (d & 1) u = fa[i][u];
  }
  return u;
}
void build(int v, int tpv) {
  int i;
  cid[v] = tick++;
  tpver[v] = tpv;
  if (mxson[v] != -1) build(mxson[v], tpv);
  for (i = 0; i < (int)adj[v].size(); ++i) {
    int u = adj[v][i];
    if (u != fa[0][v] && u != mxson[v]) {
      build(u, u);
    }
  }
}
data query(int u, int v) {
  int i, j, k;
  data ret;
  ret.set(-1, -1, 0, 0);
  if (u == -1 || v == -1) return ret;
  while (tpver[u] != tpver[v]) {
    ret = merge(ret, segT::query(1, cid[tpver[u]], cid[u]));
    u = fa[0][tpver[u]];
  }
  ret = merge(ret, segT::query(1, cid[v], cid[u]));
  return ret;
}
data queryfull(int u, int v) {
  int f = lca(u, v);
  int fv = jump(v, dep[v] - dep[f] - 1), fu = jump(u, dep[u] - dep[f] - 1);
  return merge(query(u, fu), rev(query(v, fv)));
}
void set1(int v) { segT::set1(1, cid[v]); }
};  // namespace HLD
pair<int, pair<int, int> > eds[100005];
int res[100005], u[100005], v[100005];
pair<int, int> qs[100005];
int main() {
  int i, j, k;
  scanf("%d%d", &n, &q);
  for (i = 1; i < n; ++i) scanf("%d", f + i);
  for (i = 0; i < n - 1; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    --u;
    --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
    eds[i] = make_pair(w, make_pair(u, v));
  }
  for (i = 0; i < q; ++i) {
    scanf("%d%d%d", u + i, v + i, &k);
    --u[i];
    --v[i];
    qs[i] = make_pair(k, i);
  }
  sort(eds, eds + n - 1);
  sort(qs, qs + q);
  segT::init(1);
  HLD::tick = 0;
  HLD::pdfs(0, -1);
  HLD::build(0, 0);
  HLD::precal();
  int ptr = n - 2;
  for (i = q - 1; i >= 0; --i) {
    int id = qs[i].second, w = qs[i].first;
    while (ptr >= 0 && eds[ptr].first >= w) {
      int u = eds[ptr].second.first, v = eds[ptr].second.second;
      HLD::set1(HLD::dep[u] < HLD::dep[v] ? v : u);
      --ptr;
    }
    res[id] = HLD::queryfull(u[id], v[id]).cost;
  }
  for (i = 0; i < q; ++i) printf("%d\n", res[i]);
  return 0;
}

```