#include <bits/stdc++.h>
using namespace std;
int f[200005], head[200005], size[200005], fa[200005], deep[200005],
    son[200005], dfn[200005], top[200005], pos[200005], Ans[200005];
struct ff {
  int to, nxt;
} e[200005 << 1];
struct xx {
  int l, r, w, len;
} T[200005 << 2], ans;
struct Ask {
  int u, v, w, node;
  bool operator<(const Ask& p) const {
    if (w == p.w) return node < p.node;
    return w > p.w;
  }
} a[200005 << 1];
int n, m, cnt, i, j, p, Time;
vector<int> lu, lv, ru, rv;
int fast() {
  int t = 0, fl = 1;
  char s = getchar();
  while (s < 48 || s > 57) {
    if (s == '-') fl = -1;
    s = getchar();
  }
  while (s > 47 && s < 58) t = t * 10 + s - 48, s = getchar();
  return t * fl;
}
void add(int u, int v) {
  e[++cnt] = (ff){v, head[u]};
  head[u] = cnt;
}
void dfs(int now) {
  size[now] = 1;
  for (int i = head[now]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == fa[now]) continue;
    fa[v] = now;
    pos[i / 2] = v, deep[v] = deep[now] + 1;
    dfs(v);
    size[now] += size[v];
    if (size[v] >= size[son[now]]) son[now] = v;
  }
}
void Dfs(int now) {
  dfn[now] = ++Time;
  if (son[now]) {
    top[son[now]] = top[now];
    Dfs(son[now]);
  }
  for (int i = head[now]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == fa[now] || v == son[now]) continue;
    top[v] = v;
    Dfs(v);
  }
}
void find(int u, int v) {
  lu.resize(0), ru.resize(0);
  lv.resize(0), rv.resize(0);
  int f1 = top[u], f2 = top[v];
  while (f1 != f2)
    if (deep[f1] > deep[f2]) {
      lu.push_back(dfn[f1]), ru.push_back(dfn[u]);
      u = fa[f1], f1 = top[u];
    } else {
      lv.push_back(dfn[f2]), rv.push_back(dfn[v]);
      v = fa[f2], f2 = top[v];
    }
  if (deep[u] == deep[v]) return;
  if (deep[u] > deep[v]) lu.push_back(dfn[v] + 1), ru.push_back(dfn[u]);
  if (deep[v] > deep[u]) lv.push_back(dfn[u] + 1), rv.push_back(dfn[v]);
}
xx merge(xx p, xx q) {
  xx res;
  res.w = p.w + q.w;
  res.len = p.len + q.len;
  if (p.l == p.len)
    res.l = p.len + q.l;
  else
    res.l = p.l;
  if (q.r == q.len)
    res.r = q.len + p.r;
  else
    res.r = q.r;
  if (p.l < p.len && q.r < q.len) res.w += f[p.r + q.l];
  return res;
}
void build(int l, int r, int node) {
  if (l == r) {
    T[node] = (xx){0, 0, 0, 1};
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, node << 1), build(mid + 1, r, node << 1 | 1);
  T[node] = merge(T[node << 1], T[node << 1 | 1]);
}
void change(int l, int r, int x, int node) {
  if (l == r) {
    T[node] = (xx){1, 1, 0, 1};
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    change(l, mid, x, node << 1);
  else
    change(mid + 1, r, x, node << 1 | 1);
  T[node] = merge(T[node << 1], T[node << 1 | 1]);
}
xx ask(int l, int r, int a, int b, int node) {
  if (l == a && r == b) return T[node];
  int mid = (l + r) >> 1;
  if (b <= mid) return ask(l, mid, a, b, node << 1);
  if (a > mid) return ask(mid + 1, r, a, b, node << 1 | 1);
  return merge(ask(l, mid, a, mid, node << 1),
               ask(mid + 1, r, mid + 1, b, node << 1 | 1));
}
int main() {
  n = fast(), m = fast();
  for (i = 1; i < n; i++) f[i] = fast();
  cnt = 1;
  for (i = 1; i < n; i++) {
    a[i].u = fast(), a[i].v = fast(), a[i].w = fast(), a[i].node = i;
    add(a[i].u, a[i].v), add(a[i].v, a[i].u);
  }
  fa[1] = 1, dfs(1);
  top[1] = 1, Dfs(1);
  for (i = 0; i < m; i++)
    a[i + n].u = fast(), a[i + n].v = fast(), a[i + n].w = fast(),
          a[i + n].node = n + i;
  sort(a + 1, a + n + m);
  build(1, n, 1);
  for (i = 1; i < n + m; i++)
    if (a[i].node < n)
      change(1, n, dfn[pos[a[i].node]], 1);
    else {
      ans = (xx){0, 0, 0, 0};
      p = a[i].node - n;
      find(a[i].u, a[i].v);
      for (j = 0; j < lu.size(); j++) {
        xx now = ask(1, n, lu[j], ru[j], 1);
        swap(now.l, now.r);
        ans = merge(ans, now);
      }
      for (j = lv.size() - 1; j >= 0; j--)
        ans = merge(ans, ask(1, n, lv[j], rv[j], 1));
      if (ans.l < ans.len && ans.r < ans.len)
        ans.w += f[ans.l] + f[ans.r];
      else
        ans.w += f[ans.len];
      Ans[p] = ans.w;
    }
  for (i = 0; i < m; i++) printf("%d\n", Ans[i]);
  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;
int f[200005], head[200005], size[200005], fa[200005], deep[200005],
    son[200005], dfn[200005], top[200005], pos[200005], Ans[200005];
struct ff {
  int to, nxt;
} e[200005 << 1];
struct xx {
  int l, r, w, len;
} T[200005 << 2], ans;
struct Ask {
  int u, v, w, node;
  bool operator<(const Ask& p) const {
    if (w == p.w) return node < p.node;
    return w > p.w;
  }
} a[200005 << 1];
int n, m, cnt, i, j, p, Time;
vector<int> lu, lv, ru, rv;
int fast() {
  int t = 0, fl = 1;
  char s = getchar();
  while (s < 48 || s > 57) {
    if (s == '-') fl = -1;
    s = getchar();
  }
  while (s > 47 && s < 58) t = t * 10 + s - 48, s = getchar();
  return t * fl;
}
void add(int u, int v) {
  e[++cnt] = (ff){v, head[u]};
  head[u] = cnt;
}
void dfs(int now) {
  size[now] = 1;
  for (int i = head[now]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == fa[now]) continue;
    fa[v] = now;
    pos[i / 2] = v, deep[v] = deep[now] + 1;
    dfs(v);
    size[now] += size[v];
    if (size[v] >= size[son[now]]) son[now] = v;
  }
}
void Dfs(int now) {
  dfn[now] = ++Time;
  if (son[now]) {
    top[son[now]] = top[now];
    Dfs(son[now]);
  }
  for (int i = head[now]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == fa[now] || v == son[now]) continue;
    top[v] = v;
    Dfs(v);
  }
}
void find(int u, int v) {
  lu.resize(0), ru.resize(0);
  lv.resize(0), rv.resize(0);
  int f1 = top[u], f2 = top[v];
  while (f1 != f2)
    if (deep[f1] > deep[f2]) {
      lu.push_back(dfn[f1]), ru.push_back(dfn[u]);
      u = fa[f1], f1 = top[u];
    } else {
      lv.push_back(dfn[f2]), rv.push_back(dfn[v]);
      v = fa[f2], f2 = top[v];
    }
  if (deep[u] == deep[v]) return;
  if (deep[u] > deep[v]) lu.push_back(dfn[v] + 1), ru.push_back(dfn[u]);
  if (deep[v] > deep[u]) lv.push_back(dfn[u] + 1), rv.push_back(dfn[v]);
}
xx merge(xx p, xx q) {
  xx res;
  res.w = p.w + q.w;
  res.len = p.len + q.len;
  if (p.l == p.len)
    res.l = p.len + q.l;
  else
    res.l = p.l;
  if (q.r == q.len)
    res.r = q.len + p.r;
  else
    res.r = q.r;
  if (p.l < p.len && q.r < q.len) res.w += f[p.r + q.l];
  return res;
}
void build(int l, int r, int node) {
  if (l == r) {
    T[node] = (xx){0, 0, 0, 1};
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, node << 1), build(mid + 1, r, node << 1 | 1);
  T[node] = merge(T[node << 1], T[node << 1 | 1]);
}
void change(int l, int r, int x, int node) {
  if (l == r) {
    T[node] = (xx){1, 1, 0, 1};
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    change(l, mid, x, node << 1);
  else
    change(mid + 1, r, x, node << 1 | 1);
  T[node] = merge(T[node << 1], T[node << 1 | 1]);
}
xx ask(int l, int r, int a, int b, int node) {
  if (l == a && r == b) return T[node];
  int mid = (l + r) >> 1;
  if (b <= mid) return ask(l, mid, a, b, node << 1);
  if (a > mid) return ask(mid + 1, r, a, b, node << 1 | 1);
  return merge(ask(l, mid, a, mid, node << 1),
               ask(mid + 1, r, mid + 1, b, node << 1 | 1));
}
int main() {
  n = fast(), m = fast();
  for (i = 1; i < n; i++) f[i] = fast();
  cnt = 1;
  for (i = 1; i < n; i++) {
    a[i].u = fast(), a[i].v = fast(), a[i].w = fast(), a[i].node = i;
    add(a[i].u, a[i].v), add(a[i].v, a[i].u);
  }
  fa[1] = 1, dfs(1);
  top[1] = 1, Dfs(1);
  for (i = 0; i < m; i++)
    a[i + n].u = fast(), a[i + n].v = fast(), a[i + n].w = fast(),
          a[i + n].node = n + i;
  sort(a + 1, a + n + m);
  build(1, n, 1);
  for (i = 1; i < n + m; i++)
    if (a[i].node < n)
      change(1, n, dfn[pos[a[i].node]], 1);
    else {
      ans = (xx){0, 0, 0, 0};
      p = a[i].node - n;
      find(a[i].u, a[i].v);
      for (j = 0; j < lu.size(); j++) {
        xx now = ask(1, n, lu[j], ru[j], 1);
        swap(now.l, now.r);
        ans = merge(ans, now);
      }
      for (j = lv.size() - 1; j >= 0; j--)
        ans = merge(ans, ask(1, n, lv[j], rv[j], 1));
      if (ans.l < ans.len && ans.r < ans.len)
        ans.w += f[ans.l] + f[ans.r];
      else
        ans.w += f[ans.len];
      Ans[p] = ans.w;
    }
  for (i = 0; i < m; i++) printf("%d\n", Ans[i]);
  return 0;
}

```