#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
inline T1 max(T1 a, T2 b) {
  return a < b ? b : a;
}
template <typename T1, typename T2>
inline T1 min(T1 a, T2 b) {
  return a < b ? a : b;
}
const char lf = '\n';
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
  if (s == t) {
    t = (s = buf) + fread(buf, 1, bufl, stdin);
    if (s == t) return EOF;
  }
  return *s++;
}
inline int ty() {
  int a = 0;
  int b = 1, c = fetch();
  while (!isdigit(c)) b ^= c == '-', c = fetch();
  while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
  return b ? a : -a;
}
}  // namespace ae86
using ae86::ty;
const int _ = 200007, __ = _ << 1;
vector<int> e[_];
inline void adde(int a, int b) { e[a].emplace_back(b); }
inline void addde(int a, int b) { adde(a, b), adde(b, a); }
int fa[_] = {0}, dep[_] = {0}, sz[_] = {0}, mxch[_] = {0};
void dfs(int x, int ff) {
  fa[x] = ff, dep[x] = dep[ff] + 1, sz[x] = 1, mxch[x] = 0;
  for (auto b : e[x]) {
    if (b == ff) continue;
    dfs(b, x), sz[x] += sz[b];
    if (sz[mxch[x]] < sz[b]) mxch[x] = b;
  }
}
int dfn[_] = {0}, rdfn[_] = {0}, dcnt = 0, top[_] = {0};
void dfs2(int x, int tp) {
  dfn[x] = ++dcnt, rdfn[dcnt] = x, top[x] = tp;
  if (mxch[x]) dfs2(mxch[x], tp);
  for (auto b : e[x])
    if (b != fa[x] && b != mxch[x]) dfs2(b, b);
}
int lca(int a, int b) {
  while (top[a] != top[b]) {
    if (dep[top[a]] < dep[top[b]]) swap(a, b);
    a = fa[top[a]];
  }
  if (dep[a] > dep[b]) swap(a, b);
  return a;
}
int n, qn, val[_];
struct dlq {
  long long sum;
  int len, ll, rr;
  dlq(long long sum_ = 0, int len_ = 0, int ll_ = 0, int rr_ = 0) {
    sum = sum_, len = len_, ll = ll_, rr = rr_;
  }
  friend dlq operator+(dlq a, dlq b) {
    dlq c;
    c.sum = a.sum + b.sum, c.len = a.len + b.len;
    c.ll = a.ll, c.rr = b.rr;
    if (a.ll == a.len) c.ll += b.ll;
    if (b.rr == b.len) c.rr += a.rr;
    c.sum += val[a.rr + b.ll] - val[a.rr] - val[b.ll];
    return c;
  }
};
struct sgt {
  static const int _t = _ << 2;
  dlq t[_t];
  void up(int x) { t[x] = t[(x << 1)] + t[(x << 1 | 1)]; }
  void plant(int x, int l, int r) {
    t[x] = dlq(0, r - l + 1, 0, 0);
    if (l == r) return;
    plant((x << 1), l, ((l + r) >> 1)),
        plant((x << 1 | 1), ((l + r) >> 1) + 1, r);
  }
  void change(int x, int l, int r, int tar) {
    if (l == r) {
      t[x] = dlq(val[1], 1, 1, 1);
      return;
    }
    if (tar <= ((l + r) >> 1))
      change((x << 1), l, ((l + r) >> 1), tar);
    else
      change((x << 1 | 1), ((l + r) >> 1) + 1, r, tar);
    up(x);
  }
  dlq finder(int x, int l, int r, int tl, int tr) {
    if (tl <= l && r <= tr) return t[x];
    if (tr <= ((l + r) >> 1))
      return finder((x << 1), l, ((l + r) >> 1), tl, tr);
    if (tl > ((l + r) >> 1))
      return finder((x << 1 | 1), ((l + r) >> 1) + 1, r, tl, tr);
    return finder((x << 1), l, ((l + r) >> 1), tl, tr) +
           finder((x << 1 | 1), ((l + r) >> 1) + 1, r, tl, tr);
  }
} t;
dlq finder(int x, int ff) {
  dlq ans;
  while (dep[top[x]] > dep[ff])
    ans = t.finder(1, 1, n, dfn[top[x]], dfn[x]) + ans, x = fa[top[x]];
  if (x != ff) ans = t.finder(1, 1, n, dfn[ff] + 1, dfn[x]) + ans;
  return ans;
}
struct cxk {
  int id, a, b, c;
  cxk(int id_ = 0, int a_ = 0, int b_ = 0, int c_ = 0) {
    id = id_, a = a_, b = b_, c = c_;
  }
  friend int operator<(cxk a, cxk b) {
    if (a.c == b.c) return a.id < b.id;
    return a.c > b.c;
  }
} qry[_];
int qcnt = 0;
long long ans[_] = {0};
int main() {
  ios::sync_with_stdio(0), cout.tie(nullptr);
  n = ty(), qn = ty();
  for (int i = 1; i < n; i++) val[i] = ty();
  for (int i = 1, a, b, c; i < n; i++)
    a = ty(), b = ty(), c = ty(), qry[++qcnt] = cxk(0, a, b, c), addde(a, b);
  for (int i = 1, a, b, c; i <= qn; i++)
    a = ty(), b = ty(), c = ty(), qry[++qcnt] = cxk(i, a, b, c);
  dfs(1, 0), dfs2(1, 1);
  t.plant(1, 1, n);
  sort(qry + 1, qry + qcnt + 1);
  for (int i = 1; i <= qcnt; i++) {
    if (qry[i].id == 0) {
      int a = qry[i].a, b = qry[i].b;
      if (fa[b] == a) swap(a, b);
      t.change(1, 1, n, dfn[a]);
    } else {
      int a = qry[i].a, b = qry[i].b, c = lca(a, b);
      dlq ll = finder(a, c), rr = finder(b, c);
      swap(ll.ll, ll.rr), rr = ll + rr;
      ans[qry[i].id] = rr.sum;
    }
  }
  for (int i = 1; i <= qn; i++) cout << ans[i] << lf;
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 <typename T1, typename T2>
inline T1 max(T1 a, T2 b) {
  return a < b ? b : a;
}
template <typename T1, typename T2>
inline T1 min(T1 a, T2 b) {
  return a < b ? a : b;
}
const char lf = '\n';
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
  if (s == t) {
    t = (s = buf) + fread(buf, 1, bufl, stdin);
    if (s == t) return EOF;
  }
  return *s++;
}
inline int ty() {
  int a = 0;
  int b = 1, c = fetch();
  while (!isdigit(c)) b ^= c == '-', c = fetch();
  while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
  return b ? a : -a;
}
}  // namespace ae86
using ae86::ty;
const int _ = 200007, __ = _ << 1;
vector<int> e[_];
inline void adde(int a, int b) { e[a].emplace_back(b); }
inline void addde(int a, int b) { adde(a, b), adde(b, a); }
int fa[_] = {0}, dep[_] = {0}, sz[_] = {0}, mxch[_] = {0};
void dfs(int x, int ff) {
  fa[x] = ff, dep[x] = dep[ff] + 1, sz[x] = 1, mxch[x] = 0;
  for (auto b : e[x]) {
    if (b == ff) continue;
    dfs(b, x), sz[x] += sz[b];
    if (sz[mxch[x]] < sz[b]) mxch[x] = b;
  }
}
int dfn[_] = {0}, rdfn[_] = {0}, dcnt = 0, top[_] = {0};
void dfs2(int x, int tp) {
  dfn[x] = ++dcnt, rdfn[dcnt] = x, top[x] = tp;
  if (mxch[x]) dfs2(mxch[x], tp);
  for (auto b : e[x])
    if (b != fa[x] && b != mxch[x]) dfs2(b, b);
}
int lca(int a, int b) {
  while (top[a] != top[b]) {
    if (dep[top[a]] < dep[top[b]]) swap(a, b);
    a = fa[top[a]];
  }
  if (dep[a] > dep[b]) swap(a, b);
  return a;
}
int n, qn, val[_];
struct dlq {
  long long sum;
  int len, ll, rr;
  dlq(long long sum_ = 0, int len_ = 0, int ll_ = 0, int rr_ = 0) {
    sum = sum_, len = len_, ll = ll_, rr = rr_;
  }
  friend dlq operator+(dlq a, dlq b) {
    dlq c;
    c.sum = a.sum + b.sum, c.len = a.len + b.len;
    c.ll = a.ll, c.rr = b.rr;
    if (a.ll == a.len) c.ll += b.ll;
    if (b.rr == b.len) c.rr += a.rr;
    c.sum += val[a.rr + b.ll] - val[a.rr] - val[b.ll];
    return c;
  }
};
struct sgt {
  static const int _t = _ << 2;
  dlq t[_t];
  void up(int x) { t[x] = t[(x << 1)] + t[(x << 1 | 1)]; }
  void plant(int x, int l, int r) {
    t[x] = dlq(0, r - l + 1, 0, 0);
    if (l == r) return;
    plant((x << 1), l, ((l + r) >> 1)),
        plant((x << 1 | 1), ((l + r) >> 1) + 1, r);
  }
  void change(int x, int l, int r, int tar) {
    if (l == r) {
      t[x] = dlq(val[1], 1, 1, 1);
      return;
    }
    if (tar <= ((l + r) >> 1))
      change((x << 1), l, ((l + r) >> 1), tar);
    else
      change((x << 1 | 1), ((l + r) >> 1) + 1, r, tar);
    up(x);
  }
  dlq finder(int x, int l, int r, int tl, int tr) {
    if (tl <= l && r <= tr) return t[x];
    if (tr <= ((l + r) >> 1))
      return finder((x << 1), l, ((l + r) >> 1), tl, tr);
    if (tl > ((l + r) >> 1))
      return finder((x << 1 | 1), ((l + r) >> 1) + 1, r, tl, tr);
    return finder((x << 1), l, ((l + r) >> 1), tl, tr) +
           finder((x << 1 | 1), ((l + r) >> 1) + 1, r, tl, tr);
  }
} t;
dlq finder(int x, int ff) {
  dlq ans;
  while (dep[top[x]] > dep[ff])
    ans = t.finder(1, 1, n, dfn[top[x]], dfn[x]) + ans, x = fa[top[x]];
  if (x != ff) ans = t.finder(1, 1, n, dfn[ff] + 1, dfn[x]) + ans;
  return ans;
}
struct cxk {
  int id, a, b, c;
  cxk(int id_ = 0, int a_ = 0, int b_ = 0, int c_ = 0) {
    id = id_, a = a_, b = b_, c = c_;
  }
  friend int operator<(cxk a, cxk b) {
    if (a.c == b.c) return a.id < b.id;
    return a.c > b.c;
  }
} qry[_];
int qcnt = 0;
long long ans[_] = {0};
int main() {
  ios::sync_with_stdio(0), cout.tie(nullptr);
  n = ty(), qn = ty();
  for (int i = 1; i < n; i++) val[i] = ty();
  for (int i = 1, a, b, c; i < n; i++)
    a = ty(), b = ty(), c = ty(), qry[++qcnt] = cxk(0, a, b, c), addde(a, b);
  for (int i = 1, a, b, c; i <= qn; i++)
    a = ty(), b = ty(), c = ty(), qry[++qcnt] = cxk(i, a, b, c);
  dfs(1, 0), dfs2(1, 1);
  t.plant(1, 1, n);
  sort(qry + 1, qry + qcnt + 1);
  for (int i = 1; i <= qcnt; i++) {
    if (qry[i].id == 0) {
      int a = qry[i].a, b = qry[i].b;
      if (fa[b] == a) swap(a, b);
      t.change(1, 1, n, dfn[a]);
    } else {
      int a = qry[i].a, b = qry[i].b, c = lca(a, b);
      dlq ll = finder(a, c), rr = finder(b, c);
      swap(ll.ll, ll.rr), rr = ll + rr;
      ans[qry[i].id] = rr.sum;
    }
  }
  for (int i = 1; i <= qn; i++) cout << ans[i] << lf;
  return 0;
}

```