#include <bits/stdc++.h>
long long gi() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) f ^= ch == '-', ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return f ? x : -x;
}
std::mt19937 rnd(time(NULL));
template <class T>
void cxk(T& a, T b) {
  a = a > b ? a : b;
}
template <class T>
void cnk(T& a, T b) {
  a = a < b ? a : b;
}
int f[100010];
int qa[100010], qb[100010], qc[100010], st[100010], ans[100010];
int fir[100010], dis[200010], nxt[200010], id;
void link(int a, int b) { nxt[++id] = fir[a], fir[a] = id, dis[id] = b; }
std::pair<int, std::pair<int, int> > edge[100010];
struct data {
  int L, R, sum, all;
};
data operator+(data a, data b) {
  if (a.all && b.all) return {a.R + b.L, a.R + b.L, 0, 1};
  if (a.all) return {a.R + b.L, b.R, b.sum, 0};
  if (b.all) return {a.L, a.R + b.L, a.sum, 0};
  return {a.L, b.R, a.sum + b.sum + f[a.R + b.L], 0};
}
int fa[100010], top[100010], siz[100010], son[100010], dep[100010];
void dfs(int x) {
  siz[x] = 1;
  for (int i = fir[x]; i; i = nxt[i]) {
    if (dis[i] == fa[x]) continue;
    fa[dis[i]] = x;
    dep[dis[i]] = dep[x] + 1;
    dfs(dis[i]);
    siz[x] += siz[dis[i]];
    if (siz[son[x]] < siz[dis[i]]) son[x] = dis[i];
  }
}
int dfn[100010], end[100010];
void dfs(int x, int tp) {
  dfn[x] = ++dfn[0];
  top[x] = tp;
  if (son[x]) dfs(son[x], tp);
  for (int i = fir[x]; i; i = nxt[i])
    if (dis[i] != fa[x] && dis[i] != son[x]) dfs(dis[i], dis[i]);
}
data seg[400010];
void update(int x, int l, int r, int p) {
  if (l == r) {
    seg[x] = {1, 1, 0, 1};
    return;
  }
  if (p <= ((l + r) >> 1))
    update(x << 1, l, ((l + r) >> 1), p);
  else
    update(x << 1 | 1, ((l + r) >> 1) + 1, r, p);
  seg[x] = seg[x << 1] + seg[x << 1 | 1];
}
data query(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return seg[x];
  if (L <= ((l + r) >> 1))
    if (((l + r) >> 1) < R)
      return query(x << 1, l, ((l + r) >> 1), L, R) +
             query(x << 1 | 1, ((l + r) >> 1) + 1, r, L, R);
    else
      return query(x << 1, l, ((l + r) >> 1), L, R);
  else
    return query(x << 1 | 1, ((l + r) >> 1) + 1, r, L, R);
}
int main() {
  int n = gi(), q = gi(), a, b, c;
  for (int i = 1; i < n; ++i) f[i] = gi();
  for (int i = 1; i < n; ++i)
    a = gi(), b = gi(), c = gi(), link(b, a), link(a, b), edge[i] = {c, {a, b}};
  dfs(1);
  dfs(1, 1);
  std::sort(edge + 1, edge + n);
  for (int i = 1; i <= q; ++i)
    qa[i] = gi(), qb[i] = gi(), qc[i] = gi(), st[i] = i;
  std::sort(st + 1, st + q + 1, [&](int a, int b) { return qc[a] < qc[b]; });
  for (int _ = q, i, j = n - 1; _; --_) {
    i = st[_];
    while (j && qc[i] <= edge[j].first)
      update(1, 1, n,
             std::max(dfn[edge[j].second.first], dfn[edge[j].second.second])),
          --j;
    a = qa[i], b = qb[i];
    data sa, sb;
    sa = sb = {0, 0, 0, 1};
    while (top[a] ^ top[b])
      if (dep[top[a]] > dep[top[b]])
        sa = query(1, 1, n, dfn[top[a]], dfn[a]) + sa, a = fa[top[a]];
      else
        sb = query(1, 1, n, dfn[top[b]], dfn[b]) + sb, b = fa[top[b]];
    if (dep[a] < dep[b])
      sb = query(1, 1, n, dfn[a] + 1, dfn[b]) + sb;
    else if (a ^ b)
      sa = query(1, 1, n, dfn[b] + 1, dfn[a]) + sa;
    std::swap(sa.L, sa.R);
    sa = sa + sb;
    if (!sa.all)
      ans[i] = sa.sum + f[sa.L] + f[sa.R];
    else
      ans[i] += f[sa.L];
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
  return 0;
}

### Prompt

In Cpp, your task is to solve 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>
long long gi() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) f ^= ch == '-', ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return f ? x : -x;
}
std::mt19937 rnd(time(NULL));
template <class T>
void cxk(T& a, T b) {
  a = a > b ? a : b;
}
template <class T>
void cnk(T& a, T b) {
  a = a < b ? a : b;
}
int f[100010];
int qa[100010], qb[100010], qc[100010], st[100010], ans[100010];
int fir[100010], dis[200010], nxt[200010], id;
void link(int a, int b) { nxt[++id] = fir[a], fir[a] = id, dis[id] = b; }
std::pair<int, std::pair<int, int> > edge[100010];
struct data {
  int L, R, sum, all;
};
data operator+(data a, data b) {
  if (a.all && b.all) return {a.R + b.L, a.R + b.L, 0, 1};
  if (a.all) return {a.R + b.L, b.R, b.sum, 0};
  if (b.all) return {a.L, a.R + b.L, a.sum, 0};
  return {a.L, b.R, a.sum + b.sum + f[a.R + b.L], 0};
}
int fa[100010], top[100010], siz[100010], son[100010], dep[100010];
void dfs(int x) {
  siz[x] = 1;
  for (int i = fir[x]; i; i = nxt[i]) {
    if (dis[i] == fa[x]) continue;
    fa[dis[i]] = x;
    dep[dis[i]] = dep[x] + 1;
    dfs(dis[i]);
    siz[x] += siz[dis[i]];
    if (siz[son[x]] < siz[dis[i]]) son[x] = dis[i];
  }
}
int dfn[100010], end[100010];
void dfs(int x, int tp) {
  dfn[x] = ++dfn[0];
  top[x] = tp;
  if (son[x]) dfs(son[x], tp);
  for (int i = fir[x]; i; i = nxt[i])
    if (dis[i] != fa[x] && dis[i] != son[x]) dfs(dis[i], dis[i]);
}
data seg[400010];
void update(int x, int l, int r, int p) {
  if (l == r) {
    seg[x] = {1, 1, 0, 1};
    return;
  }
  if (p <= ((l + r) >> 1))
    update(x << 1, l, ((l + r) >> 1), p);
  else
    update(x << 1 | 1, ((l + r) >> 1) + 1, r, p);
  seg[x] = seg[x << 1] + seg[x << 1 | 1];
}
data query(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return seg[x];
  if (L <= ((l + r) >> 1))
    if (((l + r) >> 1) < R)
      return query(x << 1, l, ((l + r) >> 1), L, R) +
             query(x << 1 | 1, ((l + r) >> 1) + 1, r, L, R);
    else
      return query(x << 1, l, ((l + r) >> 1), L, R);
  else
    return query(x << 1 | 1, ((l + r) >> 1) + 1, r, L, R);
}
int main() {
  int n = gi(), q = gi(), a, b, c;
  for (int i = 1; i < n; ++i) f[i] = gi();
  for (int i = 1; i < n; ++i)
    a = gi(), b = gi(), c = gi(), link(b, a), link(a, b), edge[i] = {c, {a, b}};
  dfs(1);
  dfs(1, 1);
  std::sort(edge + 1, edge + n);
  for (int i = 1; i <= q; ++i)
    qa[i] = gi(), qb[i] = gi(), qc[i] = gi(), st[i] = i;
  std::sort(st + 1, st + q + 1, [&](int a, int b) { return qc[a] < qc[b]; });
  for (int _ = q, i, j = n - 1; _; --_) {
    i = st[_];
    while (j && qc[i] <= edge[j].first)
      update(1, 1, n,
             std::max(dfn[edge[j].second.first], dfn[edge[j].second.second])),
          --j;
    a = qa[i], b = qb[i];
    data sa, sb;
    sa = sb = {0, 0, 0, 1};
    while (top[a] ^ top[b])
      if (dep[top[a]] > dep[top[b]])
        sa = query(1, 1, n, dfn[top[a]], dfn[a]) + sa, a = fa[top[a]];
      else
        sb = query(1, 1, n, dfn[top[b]], dfn[b]) + sb, b = fa[top[b]];
    if (dep[a] < dep[b])
      sb = query(1, 1, n, dfn[a] + 1, dfn[b]) + sb;
    else if (a ^ b)
      sa = query(1, 1, n, dfn[b] + 1, dfn[a]) + sa;
    std::swap(sa.L, sa.R);
    sa = sa + sb;
    if (!sa.all)
      ans[i] = sa.sum + f[sa.L] + f[sa.R];
    else
      ans[i] += f[sa.L];
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
  return 0;
}

```