#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <typename T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
template <typename T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <typename T>
inline void println(T first) {
  print(first), putchar('\n');
}
template <typename T>
inline void printsp(T first) {
  print(first), putchar(' ');
}
template <class T, class T1>
inline void print(T first, T1 second) {
  printsp(first), println(second);
}
template <class T, class T1, class T2>
inline void print(T first, T1 second, T2 z) {
  printsp(first), printsp(second), println(z);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
int f[200200];
bool rev[200200];
int pa[200200], son[200200][2], val[200200], sum[200200], sz[200200],
    le[200200], ri[200200];
void push_down(int first) {
  if (rev[first]) {
    swap(son[first][0], son[first][1]);
    swap(le[first], ri[first]);
    rev[son[first][0]] ^= 1;
    rev[son[first][1]] ^= 1;
    rev[first] = 0;
  }
}
void push_up(int first) {
  int L = son[first][0], R = son[first][1];
  push_down(L);
  push_down(R);
  sz[first] = sz[L] + sz[R] + 1;
  le[first] = (le[L] == sz[L] && val[first]) ? le[L] + 1 + le[R] : le[L];
  ri[first] = (ri[R] == sz[R] && val[first]) ? ri[R] + 1 + ri[L] : ri[R];
  sum[first] = sum[L] + sum[R];
  if (val[first])
    sum[first] += f[ri[L] + le[R] + 1 >> 1] - f[ri[L] >> 1] - f[le[R] >> 1];
}
bool isroot(int first) {
  return son[pa[first]][0] != first && son[pa[first]][1] != first;
}
void down(int first) {
  if (!isroot(first)) down(pa[first]);
  push_down(first);
}
void rot(int first, int d) {
  int second = pa[first], z = pa[second];
  son[second][!d] = son[first][d];
  pa[son[first][d]] = second;
  pa[first] = pa[second];
  if (son[z][0] == second)
    son[z][0] = first;
  else if (son[z][1] == second)
    son[z][1] = first;
  pa[second] = first;
  son[first][d] = second;
  push_up(second);
}
void splay(int first) {
  down(first);
  while (!isroot(first)) {
    if (isroot(pa[first]))
      rot(first, son[pa[first]][0] == first);
    else {
      int second = pa[first], z = pa[second];
      int d = (son[z][0] == second);
      son[second][d] == first ? rot(first, !d) : rot(second, d);
      rot(first, d);
    }
  }
  push_up(first);
}
void access(int first) {
  for (int second = 0; first; first = pa[first]) {
    splay(first);
    son[first][1] = second;
    push_up(second = first);
  }
}
void make_root(int first) {
  access(first);
  splay(first);
  rev[first] ^= 1;
}
void link(int first, int second) {
  make_root(first);
  splay(first);
  pa[first] = second;
}
int u[200200], v[200200], w[200200], eid[200200];
int a[200200], b[200200], l[200200], id[200200], ans[200200];
bool cmp(int u, int v) { return l[u] < l[v]; }
bool cmp1(int u, int v) { return w[u] < w[v]; }
void Print(int u) {
  if (!u) return;
  push_down(u);
  Print(son[u][0]);
  printf("---> %d : ls=%d, rs=%d, sz=%d, le=%d, ri=%d, val=%d, sum=%d\n", u,
         son[u][0], son[u][1], sz[u], le[u], ri[u], val[u], sum[u]);
  Print(son[u][1]);
}
int main() {
  int n, m;
  gn(n, m);
  for (int i = 1; i <= n; i++) val[i] = 1;
  for (int i = 1; i < n << 1; i++) sz[i] = 1;
  for (int i = 1; i < n; i++) gn(f[i]);
  for (int i = 1; i < n; i++) {
    gn(u[i], v[i], w[i]);
    link(u[i], n + i);
    link(v[i], n + i);
    eid[i] = i;
  }
  sort(eid + 1, eid + n, cmp1);
  for (int i = 0; i < m; i++) {
    gn(a[i], b[i], l[i]);
    id[i] = i;
  }
  sort(id, id + m, cmp);
  int cur = n - 1;
  for (int i = m; i--;) {
    while (cur > 0 && w[eid[cur]] >= l[id[i]]) {
      int e = eid[cur] + n;
      make_root(e);
      access(e);
      val[e] = 1;
      cur--;
    }
    make_root(a[id[i]]);
    access(b[id[i]]);
    splay(b[id[i]]);
    ans[id[i]] = sum[b[id[i]]];
  }
  for (int i = 0; i < m; i++) println(ans[i]);
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <typename T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
template <typename T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <typename T>
inline void println(T first) {
  print(first), putchar('\n');
}
template <typename T>
inline void printsp(T first) {
  print(first), putchar(' ');
}
template <class T, class T1>
inline void print(T first, T1 second) {
  printsp(first), println(second);
}
template <class T, class T1, class T2>
inline void print(T first, T1 second, T2 z) {
  printsp(first), printsp(second), println(z);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
int f[200200];
bool rev[200200];
int pa[200200], son[200200][2], val[200200], sum[200200], sz[200200],
    le[200200], ri[200200];
void push_down(int first) {
  if (rev[first]) {
    swap(son[first][0], son[first][1]);
    swap(le[first], ri[first]);
    rev[son[first][0]] ^= 1;
    rev[son[first][1]] ^= 1;
    rev[first] = 0;
  }
}
void push_up(int first) {
  int L = son[first][0], R = son[first][1];
  push_down(L);
  push_down(R);
  sz[first] = sz[L] + sz[R] + 1;
  le[first] = (le[L] == sz[L] && val[first]) ? le[L] + 1 + le[R] : le[L];
  ri[first] = (ri[R] == sz[R] && val[first]) ? ri[R] + 1 + ri[L] : ri[R];
  sum[first] = sum[L] + sum[R];
  if (val[first])
    sum[first] += f[ri[L] + le[R] + 1 >> 1] - f[ri[L] >> 1] - f[le[R] >> 1];
}
bool isroot(int first) {
  return son[pa[first]][0] != first && son[pa[first]][1] != first;
}
void down(int first) {
  if (!isroot(first)) down(pa[first]);
  push_down(first);
}
void rot(int first, int d) {
  int second = pa[first], z = pa[second];
  son[second][!d] = son[first][d];
  pa[son[first][d]] = second;
  pa[first] = pa[second];
  if (son[z][0] == second)
    son[z][0] = first;
  else if (son[z][1] == second)
    son[z][1] = first;
  pa[second] = first;
  son[first][d] = second;
  push_up(second);
}
void splay(int first) {
  down(first);
  while (!isroot(first)) {
    if (isroot(pa[first]))
      rot(first, son[pa[first]][0] == first);
    else {
      int second = pa[first], z = pa[second];
      int d = (son[z][0] == second);
      son[second][d] == first ? rot(first, !d) : rot(second, d);
      rot(first, d);
    }
  }
  push_up(first);
}
void access(int first) {
  for (int second = 0; first; first = pa[first]) {
    splay(first);
    son[first][1] = second;
    push_up(second = first);
  }
}
void make_root(int first) {
  access(first);
  splay(first);
  rev[first] ^= 1;
}
void link(int first, int second) {
  make_root(first);
  splay(first);
  pa[first] = second;
}
int u[200200], v[200200], w[200200], eid[200200];
int a[200200], b[200200], l[200200], id[200200], ans[200200];
bool cmp(int u, int v) { return l[u] < l[v]; }
bool cmp1(int u, int v) { return w[u] < w[v]; }
void Print(int u) {
  if (!u) return;
  push_down(u);
  Print(son[u][0]);
  printf("---> %d : ls=%d, rs=%d, sz=%d, le=%d, ri=%d, val=%d, sum=%d\n", u,
         son[u][0], son[u][1], sz[u], le[u], ri[u], val[u], sum[u]);
  Print(son[u][1]);
}
int main() {
  int n, m;
  gn(n, m);
  for (int i = 1; i <= n; i++) val[i] = 1;
  for (int i = 1; i < n << 1; i++) sz[i] = 1;
  for (int i = 1; i < n; i++) gn(f[i]);
  for (int i = 1; i < n; i++) {
    gn(u[i], v[i], w[i]);
    link(u[i], n + i);
    link(v[i], n + i);
    eid[i] = i;
  }
  sort(eid + 1, eid + n, cmp1);
  for (int i = 0; i < m; i++) {
    gn(a[i], b[i], l[i]);
    id[i] = i;
  }
  sort(id, id + m, cmp);
  int cur = n - 1;
  for (int i = m; i--;) {
    while (cur > 0 && w[eid[cur]] >= l[id[i]]) {
      int e = eid[cur] + n;
      make_root(e);
      access(e);
      val[e] = 1;
      cur--;
    }
    make_root(a[id[i]]);
    access(b[id[i]]);
    splay(b[id[i]]);
    ans[id[i]] = sum[b[id[i]]];
  }
  for (int i = 0; i < m; i++) println(ans[i]);
  return 0;
}

```