#include <bits/stdc++.h>
using namespace std;
vector<int> e[131072], qs[131072];
struct pr {
  int x, y;
} po[131072];
struct pp {
  int x, y, z, id;
} qu[131072];
int f[131072], h[131072], fa[131072], sz[131072], d[131072], w[131072],
    top[131072], ans[131072];
int L[131072 * 2], R[131072 * 2], n, q, ts, x, y, z, j;
struct dt {
  int ls, rs, a, al;
  inline friend dt operator+(const dt a, const dt b) {
    dt p;
    p.a = a.a + b.a;
    if (!a.al && !b.al) p.a += f[a.rs + b.ls];
    if (a.al && b.al)
      p.al = a.al + b.al;
    else
      p.al = 0;
    p.ls = a.ls;
    if (a.al && !b.al) p.ls = a.al + b.ls;
    p.rs = b.rs;
    if (!a.al && b.al) p.rs = a.rs + b.al;
    return p;
  }
} a[131072 * 2];
inline bool pocmp(pr x, pr y) { return x.x > y.x; }
inline bool qucmp(pp x, pp y) { return x.z > y.z; }
void dfs(int x) {
  int siz = e[x].size() - 1;
  sz[x]++;
  for (int i = (0); i <= (siz); i++)
    if (fa[x] != e[x][i]) {
      int tt = e[x][i];
      h[tt] = h[x] + 1;
      fa[tt] = x;
      po[tt].y = tt;
      po[tt].x = qs[x][i];
      dfs(tt);
      sz[x] += sz[tt];
    }
}
void mrk(int x) {
  int siz = e[x].size() - 1;
  d[++ts] = x;
  w[x] = ts;
  for (int i = (0); i <= (siz); i++)
    if (fa[x] != e[x][i]) mrk(e[x][i]);
}
void cg(int x, int s) {
  if (L[s] == R[s]) {
    a[s].ls = 0;
    a[s].rs = 0;
    a[s].a = 0;
    a[s].al = 1;
    return;
  }
  if (x <= R[s * 2])
    cg(x, s * 2);
  else
    cg(x, s * 2 + 1);
  a[s] = a[s * 2] + a[s * 2 + 1];
}
dt Q(int l, int r, int x) {
  if (L[x] == l && R[x] == r) return a[x];
  if (r <= R[x * 2]) return Q(l, r, x * 2);
  if (l >= L[x * 2 + 1]) return Q(l, r, x * 2 + 1);
  return Q(l, R[x * 2], x * 2) + Q(L[x * 2 + 1], r, x * 2 + 1);
}
int main() {
  L[1] = 1;
  R[1] = 131072;
  for (int i = (1); i <= (131072 - 1); i++) {
    L[i * 2] = L[i];
    R[i * 2] = (L[i] + R[i]) / 2;
    L[i * 2 + 1] = R[i * 2] + 1;
    R[i * 2 + 1] = R[i];
  }
  scanf("%d%d", &n, &q);
  for (int i = (1); i <= (n - 1); i++) scanf("%d", &f[i]);
  for (int i = (1); i <= (n - 1); i++) {
    scanf("%d%d%d", &x, &y, &z);
    e[x].push_back(y);
    qs[x].push_back(z);
    e[y].push_back(x);
    qs[y].push_back(z);
  }
  dfs(1);
  mrk(1);
  sort(po + 1, po + n + 1, pocmp);
  top[1] = 1;
  for (int i = (2); i <= (n); i++)
    if (fa[d[i]] != d[i - 1])
      top[d[i]] = d[i];
    else
      top[d[i]] = top[d[i - 1]];
  for (int i = (1); i <= (q); i++)
    scanf("%d%d%d", &qu[i].x, &qu[i].y, &qu[i].z), qu[i].id = i;
  sort(qu + 1, qu + q + 1, qucmp);
  j = 1;
  for (int i = (1); i <= (q); i++) {
    for (; j <= n && po[j].x >= qu[i].z; j++) cg(w[po[j].y], 1);
    x = qu[i].x;
    y = qu[i].y;
    dt xx, yy, tt, we;
    int u1 = 0, u2 = 0;
    while (top[x] != top[y])
      if (h[top[x]] > h[top[y]]) {
        we = Q(w[top[x]], w[x], 1);
        int tm = we.ls;
        we.ls = we.rs;
        we.rs = tm;
        if (u1)
          xx = xx + we;
        else
          xx = we, u1 = 1;
        x = fa[top[x]];
      } else {
        we = Q(w[top[y]], w[y], 1);
        if (u2)
          yy = we + yy;
        else
          yy = we, u2 = 1;
        y = fa[top[y]];
      }
    if (h[x] > h[y]) {
      tt = Q(w[y] + 1, w[x], 1);
      int tm = tt.ls;
      tt.ls = tt.rs;
      tt.rs = tm;
    }
    if (h[y] > h[x]) tt = Q(w[x] + 1, w[y], 1);
    if (h[x] == h[y]) {
      if (u1) tt = xx;
      if (u2) tt = yy;
      if (u1 && u2) tt = xx + yy;
    } else {
      if (u1) tt = xx + tt;
      if (u2) tt = tt + yy;
    }
    if (tt.al)
      ans[qu[i].id] = f[tt.al];
    else
      ans[qu[i].id] = tt.a + f[tt.ls] + f[tt.rs];
  }
  for (int i = (1); i <= (q); i++) printf("%d\n", ans[i]);
}

### Prompt

Your task is to create 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;
vector<int> e[131072], qs[131072];
struct pr {
  int x, y;
} po[131072];
struct pp {
  int x, y, z, id;
} qu[131072];
int f[131072], h[131072], fa[131072], sz[131072], d[131072], w[131072],
    top[131072], ans[131072];
int L[131072 * 2], R[131072 * 2], n, q, ts, x, y, z, j;
struct dt {
  int ls, rs, a, al;
  inline friend dt operator+(const dt a, const dt b) {
    dt p;
    p.a = a.a + b.a;
    if (!a.al && !b.al) p.a += f[a.rs + b.ls];
    if (a.al && b.al)
      p.al = a.al + b.al;
    else
      p.al = 0;
    p.ls = a.ls;
    if (a.al && !b.al) p.ls = a.al + b.ls;
    p.rs = b.rs;
    if (!a.al && b.al) p.rs = a.rs + b.al;
    return p;
  }
} a[131072 * 2];
inline bool pocmp(pr x, pr y) { return x.x > y.x; }
inline bool qucmp(pp x, pp y) { return x.z > y.z; }
void dfs(int x) {
  int siz = e[x].size() - 1;
  sz[x]++;
  for (int i = (0); i <= (siz); i++)
    if (fa[x] != e[x][i]) {
      int tt = e[x][i];
      h[tt] = h[x] + 1;
      fa[tt] = x;
      po[tt].y = tt;
      po[tt].x = qs[x][i];
      dfs(tt);
      sz[x] += sz[tt];
    }
}
void mrk(int x) {
  int siz = e[x].size() - 1;
  d[++ts] = x;
  w[x] = ts;
  for (int i = (0); i <= (siz); i++)
    if (fa[x] != e[x][i]) mrk(e[x][i]);
}
void cg(int x, int s) {
  if (L[s] == R[s]) {
    a[s].ls = 0;
    a[s].rs = 0;
    a[s].a = 0;
    a[s].al = 1;
    return;
  }
  if (x <= R[s * 2])
    cg(x, s * 2);
  else
    cg(x, s * 2 + 1);
  a[s] = a[s * 2] + a[s * 2 + 1];
}
dt Q(int l, int r, int x) {
  if (L[x] == l && R[x] == r) return a[x];
  if (r <= R[x * 2]) return Q(l, r, x * 2);
  if (l >= L[x * 2 + 1]) return Q(l, r, x * 2 + 1);
  return Q(l, R[x * 2], x * 2) + Q(L[x * 2 + 1], r, x * 2 + 1);
}
int main() {
  L[1] = 1;
  R[1] = 131072;
  for (int i = (1); i <= (131072 - 1); i++) {
    L[i * 2] = L[i];
    R[i * 2] = (L[i] + R[i]) / 2;
    L[i * 2 + 1] = R[i * 2] + 1;
    R[i * 2 + 1] = R[i];
  }
  scanf("%d%d", &n, &q);
  for (int i = (1); i <= (n - 1); i++) scanf("%d", &f[i]);
  for (int i = (1); i <= (n - 1); i++) {
    scanf("%d%d%d", &x, &y, &z);
    e[x].push_back(y);
    qs[x].push_back(z);
    e[y].push_back(x);
    qs[y].push_back(z);
  }
  dfs(1);
  mrk(1);
  sort(po + 1, po + n + 1, pocmp);
  top[1] = 1;
  for (int i = (2); i <= (n); i++)
    if (fa[d[i]] != d[i - 1])
      top[d[i]] = d[i];
    else
      top[d[i]] = top[d[i - 1]];
  for (int i = (1); i <= (q); i++)
    scanf("%d%d%d", &qu[i].x, &qu[i].y, &qu[i].z), qu[i].id = i;
  sort(qu + 1, qu + q + 1, qucmp);
  j = 1;
  for (int i = (1); i <= (q); i++) {
    for (; j <= n && po[j].x >= qu[i].z; j++) cg(w[po[j].y], 1);
    x = qu[i].x;
    y = qu[i].y;
    dt xx, yy, tt, we;
    int u1 = 0, u2 = 0;
    while (top[x] != top[y])
      if (h[top[x]] > h[top[y]]) {
        we = Q(w[top[x]], w[x], 1);
        int tm = we.ls;
        we.ls = we.rs;
        we.rs = tm;
        if (u1)
          xx = xx + we;
        else
          xx = we, u1 = 1;
        x = fa[top[x]];
      } else {
        we = Q(w[top[y]], w[y], 1);
        if (u2)
          yy = we + yy;
        else
          yy = we, u2 = 1;
        y = fa[top[y]];
      }
    if (h[x] > h[y]) {
      tt = Q(w[y] + 1, w[x], 1);
      int tm = tt.ls;
      tt.ls = tt.rs;
      tt.rs = tm;
    }
    if (h[y] > h[x]) tt = Q(w[x] + 1, w[y], 1);
    if (h[x] == h[y]) {
      if (u1) tt = xx;
      if (u2) tt = yy;
      if (u1 && u2) tt = xx + yy;
    } else {
      if (u1) tt = xx + tt;
      if (u2) tt = tt + yy;
    }
    if (tt.al)
      ans[qu[i].id] = f[tt.al];
    else
      ans[qu[i].id] = tt.a + f[tt.ls] + f[tt.rs];
  }
  for (int i = (1); i <= (q); i++) printf("%d\n", ans[i]);
}

```