#include <bits/stdc++.h>
using namespace std;
const int NN = 101111;
int o[NN], aa[NN * 2][3], size[NN], up[NN], heavy[NN], deep[NN], fa[NN],
    pos[NN], f[NN], ans[NN];
int n, m, tot = 1, cnt, ww, ee;
inline void addedge(int p, int q, int v) {
  tot++;
  aa[tot][1] = q;
  aa[tot][2] = v;
  aa[tot][0] = o[p];
  o[p] = tot;
}
struct edge {
  int u, v, w;
  void in() {
    scanf("%d%d%d", &u, &v, &w);
    addedge(u, v, w), addedge(v, u, w);
  }
  friend bool operator<(edge a, edge b) { return a.w < b.w; }
} e[NN];
struct query {
  int u, v, l, id;
  void in(int i) {
    scanf("%d%d%d", &u, &v, &l);
    id = i;
  }
  friend bool operator<(query a, query b) { return a.l < b.l; }
} q[NN];
void lianpou() {
  static int q[NN];
  int head = 0, tail = 1, i;
  q[1] = 1;
  deep[1] = 1;
  while (head < tail) {
    int x = q[++head];
    size[x] = 1;
    for (int p = o[x]; p; p = aa[p][0]) {
      int y = aa[p][1];
      if (y == fa[x]) continue;
      fa[y] = x;
      deep[y] = deep[x] + 1;
      q[++tail] = y;
    }
  }
  for (i = n; i; i--) {
    int x = q[i], tmp = 0, mm = 0;
    for (int p = o[x]; p; p = aa[p][0]) {
      int y = aa[p][1];
      if (y == fa[x]) continue;
      size[x] += size[y];
      if (size[y] > mm) mm = size[y], tmp = y;
    }
    heavy[x] = tmp;
  }
  up[1] = 1;
  for (i = 1; i <= n; i++) {
    int x = q[i];
    if (!up[x]) up[x] = x;
    if (heavy[x]) up[heavy[x]] = up[x];
  }
  for (i = 1; i <= n; i++) {
    int x = q[i];
    if (up[x] != x) continue;
    for (; x; x = heavy[x]) pos[x] = ++cnt;
  }
}
struct ppt {
  int l, r, len, sum;
  ppt(int a = 0, int b = 0, int c = 0, int d = 0) {
    l = a;
    r = b;
    len = c;
    sum = d;
  }
  void rev() {
    int t = l;
    l = r;
    r = t;
  }
  int calc() {
    if (l == len) return f[len];
    return sum + f[l] + f[r];
  }
  friend ppt operator+(ppt a, ppt b) {
    ppt c;
    c.len = a.len + b.len;
    if (a.len == a.l) {
      c.l = a.len + b.l;
      if (b.len == b.r)
        c.r = b.len + a.r, c.sum = 0;
      else
        c.r = b.r, c.sum = b.sum;
    } else {
      c.l = a.l;
      if (b.len == b.r)
        c.r = b.len + a.r, c.sum = a.sum;
      else
        c.r = b.r, c.sum = a.sum + b.sum + f[a.r + b.l];
    }
    return c;
  }
} tr[NN * 4];
void build(int v, int l, int r) {
  if (r - l == 1) {
    tr[v] = ppt(0, 0, 1, 0);
    return;
  }
  int mid = (l + r) >> 1;
  build((v << 1), l, mid);
  build((v << 1 | 1), mid, r);
  tr[v] = tr[(v << 1)] + tr[(v << 1 | 1)];
}
void change(int v, int l, int r, int i) {
  if (r - l == 1) {
    tr[v] = ppt(1, 1, 1, 0);
    return;
  }
  int mid = (l + r) >> 1;
  if (i < mid)
    change((v << 1), l, mid, i);
  else
    change((v << 1 | 1), mid, r, i);
  tr[v] = tr[(v << 1)] + tr[(v << 1 | 1)];
}
ppt find(int v, int l, int r) {
  if (ww <= l && r <= ee) return tr[v];
  int mid = (l + r) >> 1;
  ppt res = ppt(0, 0, 0, 0);
  if (ww < mid) res = res + find((v << 1), l, mid);
  if (ee > mid) res = res + find((v << 1 | 1), mid, r);
  return res;
}
ppt get(int x, int y) {
  ppt t1, t2;
  t1 = t2 = ppt(0, 0, 0, 0);
  while (up[x] != up[y]) {
    if (deep[up[x]] < deep[up[y]]) swap(x, y), swap(t1, t2);
    ww = pos[up[x]], ee = pos[x] + 1;
    t1 = find(1, 1, n + 1) + t1;
    x = fa[up[x]];
  }
  if (deep[x] < deep[y]) swap(x, y), swap(t1, t2);
  ww = pos[y] + 1, ee = pos[x] + 1;
  ppt t = find(1, 1, n + 1);
  t2.rev();
  return t2 + t + t1;
}
int main() {
  scanf("%d%d", &n, &m);
  int i, j;
  for (i = 1; i < n; i++) scanf("%d", &f[i]);
  for (i = 1; i < n; i++) e[i].in();
  for (i = 1; i <= m; i++) q[i].in(i);
  sort(e + 1, e + n);
  sort(q + 1, q + m + 1);
  lianpou();
  for (i = 1; i < n; i++)
    if (fa[e[i].u] != e[i].v) swap(e[i].u, e[i].v);
  build(1, 1, n + 1);
  for (j = n - 1, i = m; i; i--) {
    for (; e[j].w >= q[i].l && j; j--) change(1, 1, n + 1, pos[e[j].u]);
    ans[q[i].id] = get(q[i].u, q[i].v).calc();
  }
  for (i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}

### Prompt

Please formulate a Cpp solution to 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 NN = 101111;
int o[NN], aa[NN * 2][3], size[NN], up[NN], heavy[NN], deep[NN], fa[NN],
    pos[NN], f[NN], ans[NN];
int n, m, tot = 1, cnt, ww, ee;
inline void addedge(int p, int q, int v) {
  tot++;
  aa[tot][1] = q;
  aa[tot][2] = v;
  aa[tot][0] = o[p];
  o[p] = tot;
}
struct edge {
  int u, v, w;
  void in() {
    scanf("%d%d%d", &u, &v, &w);
    addedge(u, v, w), addedge(v, u, w);
  }
  friend bool operator<(edge a, edge b) { return a.w < b.w; }
} e[NN];
struct query {
  int u, v, l, id;
  void in(int i) {
    scanf("%d%d%d", &u, &v, &l);
    id = i;
  }
  friend bool operator<(query a, query b) { return a.l < b.l; }
} q[NN];
void lianpou() {
  static int q[NN];
  int head = 0, tail = 1, i;
  q[1] = 1;
  deep[1] = 1;
  while (head < tail) {
    int x = q[++head];
    size[x] = 1;
    for (int p = o[x]; p; p = aa[p][0]) {
      int y = aa[p][1];
      if (y == fa[x]) continue;
      fa[y] = x;
      deep[y] = deep[x] + 1;
      q[++tail] = y;
    }
  }
  for (i = n; i; i--) {
    int x = q[i], tmp = 0, mm = 0;
    for (int p = o[x]; p; p = aa[p][0]) {
      int y = aa[p][1];
      if (y == fa[x]) continue;
      size[x] += size[y];
      if (size[y] > mm) mm = size[y], tmp = y;
    }
    heavy[x] = tmp;
  }
  up[1] = 1;
  for (i = 1; i <= n; i++) {
    int x = q[i];
    if (!up[x]) up[x] = x;
    if (heavy[x]) up[heavy[x]] = up[x];
  }
  for (i = 1; i <= n; i++) {
    int x = q[i];
    if (up[x] != x) continue;
    for (; x; x = heavy[x]) pos[x] = ++cnt;
  }
}
struct ppt {
  int l, r, len, sum;
  ppt(int a = 0, int b = 0, int c = 0, int d = 0) {
    l = a;
    r = b;
    len = c;
    sum = d;
  }
  void rev() {
    int t = l;
    l = r;
    r = t;
  }
  int calc() {
    if (l == len) return f[len];
    return sum + f[l] + f[r];
  }
  friend ppt operator+(ppt a, ppt b) {
    ppt c;
    c.len = a.len + b.len;
    if (a.len == a.l) {
      c.l = a.len + b.l;
      if (b.len == b.r)
        c.r = b.len + a.r, c.sum = 0;
      else
        c.r = b.r, c.sum = b.sum;
    } else {
      c.l = a.l;
      if (b.len == b.r)
        c.r = b.len + a.r, c.sum = a.sum;
      else
        c.r = b.r, c.sum = a.sum + b.sum + f[a.r + b.l];
    }
    return c;
  }
} tr[NN * 4];
void build(int v, int l, int r) {
  if (r - l == 1) {
    tr[v] = ppt(0, 0, 1, 0);
    return;
  }
  int mid = (l + r) >> 1;
  build((v << 1), l, mid);
  build((v << 1 | 1), mid, r);
  tr[v] = tr[(v << 1)] + tr[(v << 1 | 1)];
}
void change(int v, int l, int r, int i) {
  if (r - l == 1) {
    tr[v] = ppt(1, 1, 1, 0);
    return;
  }
  int mid = (l + r) >> 1;
  if (i < mid)
    change((v << 1), l, mid, i);
  else
    change((v << 1 | 1), mid, r, i);
  tr[v] = tr[(v << 1)] + tr[(v << 1 | 1)];
}
ppt find(int v, int l, int r) {
  if (ww <= l && r <= ee) return tr[v];
  int mid = (l + r) >> 1;
  ppt res = ppt(0, 0, 0, 0);
  if (ww < mid) res = res + find((v << 1), l, mid);
  if (ee > mid) res = res + find((v << 1 | 1), mid, r);
  return res;
}
ppt get(int x, int y) {
  ppt t1, t2;
  t1 = t2 = ppt(0, 0, 0, 0);
  while (up[x] != up[y]) {
    if (deep[up[x]] < deep[up[y]]) swap(x, y), swap(t1, t2);
    ww = pos[up[x]], ee = pos[x] + 1;
    t1 = find(1, 1, n + 1) + t1;
    x = fa[up[x]];
  }
  if (deep[x] < deep[y]) swap(x, y), swap(t1, t2);
  ww = pos[y] + 1, ee = pos[x] + 1;
  ppt t = find(1, 1, n + 1);
  t2.rev();
  return t2 + t + t1;
}
int main() {
  scanf("%d%d", &n, &m);
  int i, j;
  for (i = 1; i < n; i++) scanf("%d", &f[i]);
  for (i = 1; i < n; i++) e[i].in();
  for (i = 1; i <= m; i++) q[i].in(i);
  sort(e + 1, e + n);
  sort(q + 1, q + m + 1);
  lianpou();
  for (i = 1; i < n; i++)
    if (fa[e[i].u] != e[i].v) swap(e[i].u, e[i].v);
  build(1, 1, n + 1);
  for (j = n - 1, i = m; i; i--) {
    for (; e[j].w >= q[i].l && j; j--) change(1, 1, n + 1, pos[e[j].u]);
    ans[q[i].id] = get(q[i].u, q[i].v).calc();
  }
  for (i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}

```