#include <bits/stdc++.h>
int inp() {
  char c = getchar();
  int neg = 1;
  while (c < '0' || c > '9') {
    if (c == '-') neg = -1;
    c = getchar();
  }
  int sum = 0;
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  return sum * neg;
}
int idx = 0;
struct SEG {
  int l;
  int r;
  int ls;
  int rs;
  int sum;
  int len;
};
struct Node {
  int x;
  int y;
  int l;
  int id;
} q[100010];
bool cmp(Node a, Node b) { return a.l < b.l; }
int f[100010], w[100010], size[100010], top[100010], fa[100010], depth[100010],
    son[100010], dfn[100010], id[100010];
int head[100010], nxt[200010], end[200010], ans[100010], value[200010];
int cou = 0;
void link(int a, int b, int v) {
  nxt[++cou] = head[a];
  head[a] = cou;
  end[cou] = b;
  value[cou] = v;
}
bool cmp2(int a, int b) { return w[a] < w[b]; }
SEG operator+(SEG a, SEG b) {
  if (a.l == -1) return b;
  if (b.l == -1) return a;
  SEG ret;
  ret.ls = a.ls;
  ret.l = a.l;
  ret.rs = b.rs;
  ret.r = b.r;
  ret.len = a.len + b.len;
  ret.sum = a.sum + b.sum;
  ret.sum -= f[a.rs];
  ret.sum -= f[b.ls];
  ret.sum += f[a.rs + b.ls];
  if (ret.ls == a.len) ret.ls += b.ls;
  if (ret.rs == b.len) ret.rs += a.rs;
  return ret;
}
struct SEG_Tree {
  SEG t[400010];
  void push_up(int cur) { t[cur] = t[((cur) << 1)] + t[((cur) << 1 | 1)]; }
  void build(int cur, int l, int r) {
    t[cur].l = l;
    t[cur].r = r;
    t[cur].len = r - l + 1;
    if (l == r) {
      t[cur].ls = t[cur].rs = 1;
      t[cur].sum = f[1];
      return;
    }
    int mid = (l + r) >> 1;
    build(((cur) << 1), l, mid);
    build(((cur) << 1 | 1), mid + 1, r);
    push_up(cur);
  }
  void modify(int cur, int x) {
    if (t[cur].l == t[cur].r) {
      t[cur].sum = 0;
      t[cur].ls = t[cur].rs = 0;
      return;
    }
    if (x <= t[((cur) << 1)].r)
      modify(((cur) << 1), x);
    else
      modify(((cur) << 1 | 1), x);
    push_up(cur);
  }
  SEG query(int cur, int l, int r) {
    if (t[cur].l > r || t[cur].r < l) return (SEG){-1, -1, -1, -1, -1, -1};
    if (t[cur].l >= l && t[cur].r <= r) {
      if (t[cur].l == 1) printf("Sukun AKIOI\n");
      return t[cur];
    }
    return query(((cur) << 1), l, r) + query(((cur) << 1 | 1), l, r);
  }
} t;
void dfs1(int cur, int last) {
  fa[cur] = last;
  size[cur] = 1;
  depth[cur] = depth[last] + 1;
  for (int x = head[cur]; x != -1; x = nxt[x]) {
    if (end[x] != last) {
      w[end[x]] = value[x];
      dfs1(end[x], cur);
      size[cur] += size[end[x]];
      if (size[end[x]] > size[son[cur]]) son[cur] = end[x];
    }
  }
}
void dfs2(int cur, int last, int t) {
  dfn[cur] = ++idx;
  top[cur] = t;
  if (son[cur]) dfs2(son[cur], cur, t);
  for (int x = head[cur]; x != -1; x = nxt[x])
    if (end[x] != last && end[x] != son[cur]) dfs2(end[x], cur, end[x]);
}
int query(int cur, int x, int y) {
  bool t0 = false, t1 = true;
  std::vector<SEG> vec[2];
  while (top[x] != top[y]) {
    if (depth[top[x]] < depth[top[y]]) {
      std::swap(x, y);
      std::swap(t0, t1);
    }
    vec[t0].push_back(t.query(1, dfn[top[x]], dfn[x]));
    x = fa[top[x]];
  }
  if (depth[x] > depth[y]) {
    std::swap(x, y);
    std::swap(t0, t1);
  }
  SEG ans = (SEG){-1, -1, -1, -1, -1};
  for (int i = 0; i < vec[0].size(); i++) {
    std::swap(vec[0][i].ls, vec[0][i].rs);
    ans = ans + vec[0][i];
  }
  SEG mid = t.query(1, dfn[x] + 1, dfn[y]);
  if (t0) std::swap(mid.ls, mid.rs);
  ans = ans + mid;
  for (int i = vec[1].size() - 1; i >= 0; i--) {
    ans = ans + vec[1][i];
  }
  return ans.sum;
}
int main() {
  memset(head, -1, sizeof(head));
  int n = inp();
  int m = inp();
  for (int i = 1; i < n; i++) f[i] = inp();
  for (int i = 1; i < n; i++) {
    int u = inp();
    int v = inp();
    int w = inp();
    link(u, v, w);
    link(v, u, w);
  }
  dfs1(1, 0);
  dfs2(1, 0, 1);
  t.build(1, 1, n);
  for (int i = 1; i < n; i++) id[i] = i + 1;
  std::sort(id + 1, id + n, cmp2);
  for (int i = 1; i <= m; i++) {
    q[i].x = inp();
    q[i].y = inp();
    q[i].l = inp();
    q[i].id = i;
  }
  std::sort(q + 1, q + m + 1, cmp);
  int cur = 1;
  for (int i = 1; i <= m; i++) {
    while (cur < n && w[id[cur]] < q[i].l) {
      t.modify(1, dfn[id[cur]]);
      cur++;
    }
    ans[q[i].id] = query(1, q[i].x, q[i].y);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}

### 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>
int inp() {
  char c = getchar();
  int neg = 1;
  while (c < '0' || c > '9') {
    if (c == '-') neg = -1;
    c = getchar();
  }
  int sum = 0;
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  return sum * neg;
}
int idx = 0;
struct SEG {
  int l;
  int r;
  int ls;
  int rs;
  int sum;
  int len;
};
struct Node {
  int x;
  int y;
  int l;
  int id;
} q[100010];
bool cmp(Node a, Node b) { return a.l < b.l; }
int f[100010], w[100010], size[100010], top[100010], fa[100010], depth[100010],
    son[100010], dfn[100010], id[100010];
int head[100010], nxt[200010], end[200010], ans[100010], value[200010];
int cou = 0;
void link(int a, int b, int v) {
  nxt[++cou] = head[a];
  head[a] = cou;
  end[cou] = b;
  value[cou] = v;
}
bool cmp2(int a, int b) { return w[a] < w[b]; }
SEG operator+(SEG a, SEG b) {
  if (a.l == -1) return b;
  if (b.l == -1) return a;
  SEG ret;
  ret.ls = a.ls;
  ret.l = a.l;
  ret.rs = b.rs;
  ret.r = b.r;
  ret.len = a.len + b.len;
  ret.sum = a.sum + b.sum;
  ret.sum -= f[a.rs];
  ret.sum -= f[b.ls];
  ret.sum += f[a.rs + b.ls];
  if (ret.ls == a.len) ret.ls += b.ls;
  if (ret.rs == b.len) ret.rs += a.rs;
  return ret;
}
struct SEG_Tree {
  SEG t[400010];
  void push_up(int cur) { t[cur] = t[((cur) << 1)] + t[((cur) << 1 | 1)]; }
  void build(int cur, int l, int r) {
    t[cur].l = l;
    t[cur].r = r;
    t[cur].len = r - l + 1;
    if (l == r) {
      t[cur].ls = t[cur].rs = 1;
      t[cur].sum = f[1];
      return;
    }
    int mid = (l + r) >> 1;
    build(((cur) << 1), l, mid);
    build(((cur) << 1 | 1), mid + 1, r);
    push_up(cur);
  }
  void modify(int cur, int x) {
    if (t[cur].l == t[cur].r) {
      t[cur].sum = 0;
      t[cur].ls = t[cur].rs = 0;
      return;
    }
    if (x <= t[((cur) << 1)].r)
      modify(((cur) << 1), x);
    else
      modify(((cur) << 1 | 1), x);
    push_up(cur);
  }
  SEG query(int cur, int l, int r) {
    if (t[cur].l > r || t[cur].r < l) return (SEG){-1, -1, -1, -1, -1, -1};
    if (t[cur].l >= l && t[cur].r <= r) {
      if (t[cur].l == 1) printf("Sukun AKIOI\n");
      return t[cur];
    }
    return query(((cur) << 1), l, r) + query(((cur) << 1 | 1), l, r);
  }
} t;
void dfs1(int cur, int last) {
  fa[cur] = last;
  size[cur] = 1;
  depth[cur] = depth[last] + 1;
  for (int x = head[cur]; x != -1; x = nxt[x]) {
    if (end[x] != last) {
      w[end[x]] = value[x];
      dfs1(end[x], cur);
      size[cur] += size[end[x]];
      if (size[end[x]] > size[son[cur]]) son[cur] = end[x];
    }
  }
}
void dfs2(int cur, int last, int t) {
  dfn[cur] = ++idx;
  top[cur] = t;
  if (son[cur]) dfs2(son[cur], cur, t);
  for (int x = head[cur]; x != -1; x = nxt[x])
    if (end[x] != last && end[x] != son[cur]) dfs2(end[x], cur, end[x]);
}
int query(int cur, int x, int y) {
  bool t0 = false, t1 = true;
  std::vector<SEG> vec[2];
  while (top[x] != top[y]) {
    if (depth[top[x]] < depth[top[y]]) {
      std::swap(x, y);
      std::swap(t0, t1);
    }
    vec[t0].push_back(t.query(1, dfn[top[x]], dfn[x]));
    x = fa[top[x]];
  }
  if (depth[x] > depth[y]) {
    std::swap(x, y);
    std::swap(t0, t1);
  }
  SEG ans = (SEG){-1, -1, -1, -1, -1};
  for (int i = 0; i < vec[0].size(); i++) {
    std::swap(vec[0][i].ls, vec[0][i].rs);
    ans = ans + vec[0][i];
  }
  SEG mid = t.query(1, dfn[x] + 1, dfn[y]);
  if (t0) std::swap(mid.ls, mid.rs);
  ans = ans + mid;
  for (int i = vec[1].size() - 1; i >= 0; i--) {
    ans = ans + vec[1][i];
  }
  return ans.sum;
}
int main() {
  memset(head, -1, sizeof(head));
  int n = inp();
  int m = inp();
  for (int i = 1; i < n; i++) f[i] = inp();
  for (int i = 1; i < n; i++) {
    int u = inp();
    int v = inp();
    int w = inp();
    link(u, v, w);
    link(v, u, w);
  }
  dfs1(1, 0);
  dfs2(1, 0, 1);
  t.build(1, 1, n);
  for (int i = 1; i < n; i++) id[i] = i + 1;
  std::sort(id + 1, id + n, cmp2);
  for (int i = 1; i <= m; i++) {
    q[i].x = inp();
    q[i].y = inp();
    q[i].l = inp();
    q[i].id = i;
  }
  std::sort(q + 1, q + m + 1, cmp);
  int cur = 1;
  for (int i = 1; i <= m; i++) {
    while (cur < n && w[id[cur]] < q[i].l) {
      t.modify(1, dfn[id[cur]]);
      cur++;
    }
    ans[q[i].id] = query(1, q[i].x, q[i].y);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}

```