#include <bits/stdc++.h>
using namespace std;
const int iinf = 1e9 + 7;
const long long linf = 1ll << 60;
const double dinf = 1e60;
template <typename T>
inline void scf(T &x) {
  bool f = 0;
  x = 0;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') {
    f = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  if (f) x = -x;
  return;
}
template <typename T1, typename T2>
void scf(T1 &x, T2 &y) {
  scf(x);
  return scf(y);
}
template <typename T1, typename T2, typename T3>
void scf(T1 &x, T2 &y, T3 &z) {
  scf(x);
  scf(y);
  return scf(z);
}
template <typename T1, typename T2, typename T3, typename T4>
void scf(T1 &x, T2 &y, T3 &z, T4 &w) {
  scf(x);
  scf(y);
  scf(z);
  return scf(w);
}
inline char mygetchar() {
  char c = getchar();
  while (c == ' ' || c == '\n') c = getchar();
  return c;
}
template <typename T>
void chkmax(T &x, const T &y) {
  if (y > x) x = y;
  return;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
  return;
}
const int N = 1e5 + 100;
int n, q_n, clk;
int f[N], ans[N];
struct query {
  int typ, u, v, w;
  query() {}
  query(int T, int U, int V, int W) : typ(T), u(U), v(V), w(W) {}
  bool operator<(const query &a) const {
    return w != a.w ? w > a.w : typ < a.typ;
  }
};
vector<query> q;
struct node {
  int len, num, cntl, cntr;
  node operator+(const node &a) const {
    node ret;
    ret.num = num + a.num;
    ret.len = len + a.len;
    ret.cntl = (cntl == len ? len + a.cntl : cntl);
    ret.cntr = (a.cntr == a.len ? a.len + cntr : a.cntr);
    if (ret.cntl < len && ret.cntr < a.len) ret.num += f[cntr + a.cntl];
    return ret;
  }
};
namespace seg {
const int hN = 1 << 17;
node f[hN << 1];
void I() {
  for (int i = 0; i < (hN + hN); ++i) f[i].num = f[i].cntl = f[i].cntr = 0;
  for (int i = (1); i <= (n); ++i) f[i | hN].len = 1;
  for (int i = (hN)-1; i >= 0; --i) f[i] = f[i << 1] + f[(i << 1) | 1];
  return;
}
void M(int i) {
  i |= hN;
  f[i].cntl = f[i].cntr = 1;
  f[i].num = 0;
  f[i].len = 1;
  i >>= 1;
  while (i) f[i] = f[i << 1] + f[(i << 1) | 1], i >>= 1;
  return;
}
node Q(int s, int t) {
  node l, r;
  l.len = r.len = l.num = r.num = l.cntl = r.cntl = l.cntr = r.cntr = 0;
  for (s |= hN, t |= hN, s--, t++; s ^ t ^ 1; s >>= 1, t >>= 1) {
    if (~s & 1) l = l + f[s ^ 1];
    if (t & 1) r = f[t ^ 1] + r;
  }
  return l + r;
}
}  // namespace seg
vector<int> g[N];
int son[N], hs[N], anc[N], par[N], dep[N], siz[N], dfn[N];
namespace HLD {
void dfs1(int u = 1, int fa = 0) {
  par[u] = fa;
  dep[u] = dep[fa] + 1;
  siz[u] = 1;
  for (int v : g[u])
    if (v != fa) {
      dfs1(v, u);
      siz[u] += siz[v];
      if (siz[v] > hs[u]) hs[u] = siz[v], son[u] = v;
    }
  return;
}
void dfs2(int u = 1, int fa = 1) {
  anc[u] = fa;
  dfn[u] = (++clk);
  if (son[u]) dfs2(son[u], fa);
  for (int v : g[u])
    if (v != par[u] && v != son[u]) dfs2(v, v);
  return;
}
void doit() {
  dfs1();
  dfs2();
}
void M(int u, int v) {
  if (u == par[v]) swap(u, v);
  return seg::M(dfn[u]);
}
int Q(int u, int v) {
  node l, r;
  l.len = r.len = l.num = r.num = l.cntl = r.cntl = l.cntr = r.cntr = 0;
  while (anc[u] != anc[v]) {
    if (dep[anc[u]] < dep[anc[v]]) {
      r = seg::Q(dfn[anc[v]], dfn[v]) + r;
      v = par[anc[v]];
    } else {
      l = seg::Q(dfn[anc[u]], dfn[u]) + l;
      u = par[anc[u]];
    }
  }
  if (dep[u] > dep[v])
    l = seg::Q(dfn[v] + 1, dfn[u]) + l;
  else
    r = seg::Q(dfn[u] + 1, dfn[v]) + r;
  swap(l.cntl, l.cntr);
  int ret = l.num + r.num;
  if (l.cntl == l.len && r.cntr == r.len)
    ret += f[l.len + r.len];
  else if (l.cntl == l.len)
    ret += f[l.len + r.cntl] + f[r.cntr];
  else if (r.cntr == r.len)
    ret += f[r.len + l.cntr] + f[l.cntl];
  else
    ret += f[l.cntl] + f[l.cntr + r.cntl] + f[r.cntr];
  return ret;
}
}  // namespace HLD
void TZL() {
  scf(n, q_n);
  for (int i = (1); i <= (n - 1); ++i) scf(f[i]);
  for (int i = 0; i < (n - 1); ++i) {
    int u, v, w;
    scf(u, v, w);
    g[u].push_back(v);
    g[v].push_back(u);
    q.push_back(query(0, u, v, w));
  }
  for (int i = (1); i <= (q_n); ++i) {
    int u, v, w;
    scf(u, v, w);
    q.push_back(query(i, u, v, w));
  }
  sort(q.begin(), q.end());
  HLD::doit();
  seg::I();
  return;
}
void RANK1() {
  for (query t : q) {
    int u = t.u, v = t.v, typ = t.typ;
    if (!t.typ)
      HLD::M(u, v);
    else
      ans[t.typ] = HLD::Q(u, v);
  }
  for (int i = (1); i <= (q_n); ++i) printf("%d\n", ans[i]);
  return;
}
int main() {
  TZL();
  RANK1();
  return 0;
}

### Prompt

Create a solution in cpp for 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 iinf = 1e9 + 7;
const long long linf = 1ll << 60;
const double dinf = 1e60;
template <typename T>
inline void scf(T &x) {
  bool f = 0;
  x = 0;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') {
    f = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  if (f) x = -x;
  return;
}
template <typename T1, typename T2>
void scf(T1 &x, T2 &y) {
  scf(x);
  return scf(y);
}
template <typename T1, typename T2, typename T3>
void scf(T1 &x, T2 &y, T3 &z) {
  scf(x);
  scf(y);
  return scf(z);
}
template <typename T1, typename T2, typename T3, typename T4>
void scf(T1 &x, T2 &y, T3 &z, T4 &w) {
  scf(x);
  scf(y);
  scf(z);
  return scf(w);
}
inline char mygetchar() {
  char c = getchar();
  while (c == ' ' || c == '\n') c = getchar();
  return c;
}
template <typename T>
void chkmax(T &x, const T &y) {
  if (y > x) x = y;
  return;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
  return;
}
const int N = 1e5 + 100;
int n, q_n, clk;
int f[N], ans[N];
struct query {
  int typ, u, v, w;
  query() {}
  query(int T, int U, int V, int W) : typ(T), u(U), v(V), w(W) {}
  bool operator<(const query &a) const {
    return w != a.w ? w > a.w : typ < a.typ;
  }
};
vector<query> q;
struct node {
  int len, num, cntl, cntr;
  node operator+(const node &a) const {
    node ret;
    ret.num = num + a.num;
    ret.len = len + a.len;
    ret.cntl = (cntl == len ? len + a.cntl : cntl);
    ret.cntr = (a.cntr == a.len ? a.len + cntr : a.cntr);
    if (ret.cntl < len && ret.cntr < a.len) ret.num += f[cntr + a.cntl];
    return ret;
  }
};
namespace seg {
const int hN = 1 << 17;
node f[hN << 1];
void I() {
  for (int i = 0; i < (hN + hN); ++i) f[i].num = f[i].cntl = f[i].cntr = 0;
  for (int i = (1); i <= (n); ++i) f[i | hN].len = 1;
  for (int i = (hN)-1; i >= 0; --i) f[i] = f[i << 1] + f[(i << 1) | 1];
  return;
}
void M(int i) {
  i |= hN;
  f[i].cntl = f[i].cntr = 1;
  f[i].num = 0;
  f[i].len = 1;
  i >>= 1;
  while (i) f[i] = f[i << 1] + f[(i << 1) | 1], i >>= 1;
  return;
}
node Q(int s, int t) {
  node l, r;
  l.len = r.len = l.num = r.num = l.cntl = r.cntl = l.cntr = r.cntr = 0;
  for (s |= hN, t |= hN, s--, t++; s ^ t ^ 1; s >>= 1, t >>= 1) {
    if (~s & 1) l = l + f[s ^ 1];
    if (t & 1) r = f[t ^ 1] + r;
  }
  return l + r;
}
}  // namespace seg
vector<int> g[N];
int son[N], hs[N], anc[N], par[N], dep[N], siz[N], dfn[N];
namespace HLD {
void dfs1(int u = 1, int fa = 0) {
  par[u] = fa;
  dep[u] = dep[fa] + 1;
  siz[u] = 1;
  for (int v : g[u])
    if (v != fa) {
      dfs1(v, u);
      siz[u] += siz[v];
      if (siz[v] > hs[u]) hs[u] = siz[v], son[u] = v;
    }
  return;
}
void dfs2(int u = 1, int fa = 1) {
  anc[u] = fa;
  dfn[u] = (++clk);
  if (son[u]) dfs2(son[u], fa);
  for (int v : g[u])
    if (v != par[u] && v != son[u]) dfs2(v, v);
  return;
}
void doit() {
  dfs1();
  dfs2();
}
void M(int u, int v) {
  if (u == par[v]) swap(u, v);
  return seg::M(dfn[u]);
}
int Q(int u, int v) {
  node l, r;
  l.len = r.len = l.num = r.num = l.cntl = r.cntl = l.cntr = r.cntr = 0;
  while (anc[u] != anc[v]) {
    if (dep[anc[u]] < dep[anc[v]]) {
      r = seg::Q(dfn[anc[v]], dfn[v]) + r;
      v = par[anc[v]];
    } else {
      l = seg::Q(dfn[anc[u]], dfn[u]) + l;
      u = par[anc[u]];
    }
  }
  if (dep[u] > dep[v])
    l = seg::Q(dfn[v] + 1, dfn[u]) + l;
  else
    r = seg::Q(dfn[u] + 1, dfn[v]) + r;
  swap(l.cntl, l.cntr);
  int ret = l.num + r.num;
  if (l.cntl == l.len && r.cntr == r.len)
    ret += f[l.len + r.len];
  else if (l.cntl == l.len)
    ret += f[l.len + r.cntl] + f[r.cntr];
  else if (r.cntr == r.len)
    ret += f[r.len + l.cntr] + f[l.cntl];
  else
    ret += f[l.cntl] + f[l.cntr + r.cntl] + f[r.cntr];
  return ret;
}
}  // namespace HLD
void TZL() {
  scf(n, q_n);
  for (int i = (1); i <= (n - 1); ++i) scf(f[i]);
  for (int i = 0; i < (n - 1); ++i) {
    int u, v, w;
    scf(u, v, w);
    g[u].push_back(v);
    g[v].push_back(u);
    q.push_back(query(0, u, v, w));
  }
  for (int i = (1); i <= (q_n); ++i) {
    int u, v, w;
    scf(u, v, w);
    q.push_back(query(i, u, v, w));
  }
  sort(q.begin(), q.end());
  HLD::doit();
  seg::I();
  return;
}
void RANK1() {
  for (query t : q) {
    int u = t.u, v = t.v, typ = t.typ;
    if (!t.typ)
      HLD::M(u, v);
    else
      ans[t.typ] = HLD::Q(u, v);
  }
  for (int i = (1); i <= (q_n); ++i) printf("%d\n", ans[i]);
  return;
}
int main() {
  TZL();
  RANK1();
  return 0;
}

```