#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool getmin(T *a, const T &b) {
  if (b < *a) {
    *a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool getmax(T *a, const T &b) {
  if (b > *a) {
    *a = b;
    return true;
  }
  return false;
}
template <class T>
inline void read(T *a) {
  char c;
  while (isspace(c = getchar())) {
  }
  bool flag = 0;
  if (c == '-')
    flag = 1, *a = 0;
  else
    *a = c - 48;
  while (isdigit(c = getchar())) *a = *a * 10 + c - 48;
  if (flag) *a = -*a;
}
const int mo = 1000000007;
template <class T>
T pow(T a, T b, int c = mo) {
  T res = 1;
  for (T i = 1; i <= b; i <<= 1, a = 1LL * a * a % c)
    if (b & i) res = 1LL * res * a % c;
  return res;
}
const int N = 210000;
int f[N];
int n, q;
struct node {
  int v, dl, dr, size;
} tree[N * 2];
int dfn[N], id[N], idx;
struct edge_node {
  int p, nextt, w;
} edge[N];
pair<int, int> e[N];
int head[N];
int cnt;
void ae(int a, int b, int c) {
  edge[++cnt].p = b;
  edge[cnt].w = c;
  edge[cnt].nextt = head[a];
  head[a] = cnt;
}
int dep[N], size[N];
void getsize(int u, int fa) {
  size[u] = 1;
  for (int k = head[(u)]; k; k = edge[k].nextt) {
    int v = edge[k].p;
    if (v != fa) {
      getsize(v, u);
      size[u] += size[v];
    }
  }
}
int top[N], tot, g[N];
const int inf = 1000000001;
void dfs(int u, int fa, int r, int x) {
  dfn[u] = ++idx;
  if (x != inf) e[++tot] = std::make_pair(x, idx);
  g[u] = fa;
  id[idx] = u;
  top[u] = r;
  dep[u] = dep[fa] + 1;
  int e = 0;
  for (int k = head[(u)]; k; k = edge[k].nextt) {
    int v = edge[k].p;
    if (v != fa && size[v] > size[edge[e].p]) e = k;
  }
  if (e) dfs(edge[e].p, u, r, edge[e].w);
  for (int k = head[(u)]; k; k = edge[k].nextt) {
    int v = edge[k].p;
    if (v != fa && k != e) {
      dfs(v, u, v, edge[k].w);
    }
  }
}
void update(node &A, const node &X, const node &Y) {
  A.v = X.v + Y.v - f[X.dr] - f[Y.dl] + f[X.dr + Y.dl];
  A.dl = X.dl;
  if (X.dl == X.size) A.dl += Y.dl;
  A.dr = Y.dr;
  if (Y.dr == Y.size) A.dr += X.dr;
  A.size = X.size + Y.size;
}
void add(int u, int L, int R, int p) {
  if (L == R) {
    tree[u].v = f[1];
    tree[u].dl = tree[u].dr = 1;
    return;
  }
  int mid = (L + R) >> 1;
  if (p <= mid)
    add(u * 2, L, mid, p);
  else
    add(u * 2 + 1, mid + 1, R, p);
  update(tree[u], tree[u * 2], tree[u * 2 + 1]);
}
node query(int u, int L, int R, int l, int r) {
  if (l <= L && r >= R) return tree[u];
  int mid = (L + R) >> 1;
  if (r <= mid)
    return query(u * 2, L, mid, l, r);
  else if (l > mid)
    return query(u * 2 + 1, mid + 1, R, l, r);
  else {
    node ans;
    update(ans, query(u * 2, L, mid, l, mid),
           query(u * 2 + 1, mid + 1, R, mid + 1, r));
    return ans;
  }
}
int lca(int a, int b) {
  while (top[a] != top[b]) {
    if (dep[top[a]] > dep[top[b]])
      a = g[top[a]];
    else
      b = g[top[b]];
  }
  return dep[a] < dep[b] ? a : b;
}
struct Qnode {
  int x, y, w, p;
} Q[N];
bool cmp(const Qnode &A, const Qnode &B) { return A.w < B.w; }
int ans[N];
void build(int u, int L, int R) {
  tree[u].size = R - L + 1;
  if (L == R) return;
  int mid = (L + R) >> 1;
  build(u * 2, L, mid);
  build(u * 2 + 1, mid + 1, R);
}
node ask(int a, int b) {
  node res;
  res.v = res.dl = res.dr = 0;
  res.size = 0;
  while (dep[a] > dep[b]) {
    node xx = res;
    if (dep[top[a]] > dep[top[b]])
      update(res, query(1, 1, n, dfn[top[a]], dfn[a]), xx);
    else
      update(res, query(1, 1, n, dfn[b] + 1, dfn[a]), xx);
    a = g[top[a]];
  }
  return res;
}
int main() {
  cin >> n >> q;
  for (int i = (1); i <= (n - 1); ++i) read(f + i);
  for (int i = (2); i <= (n); ++i) {
    int x, y, z;
    read(&x);
    read(&y);
    read(&z);
    ae(x, y, z);
    ae(y, x, z);
  }
  getsize(1, 0);
  dfs(1, 0, 1, inf);
  build(1, 1, n);
  sort(e + 1, e + n);
  for (int i = (1); i <= (q); ++i) {
    read(&Q[i].x);
    read(&Q[i].y);
    read(&Q[i].w);
    Q[i].p = i;
  }
  sort(Q + 1, Q + q + 1, cmp);
  int j = n - 1;
  for (int i = (q); i >= (1); --i) {
    while (j >= 1 && e[j].first >= Q[i].w) add(1, 1, n, e[j].second), --j;
    int x = Q[i].x, y = Q[i].y, z = lca(x, y);
    node A = ask(x, z), B = ask(y, z);
    ans[Q[i].p] = A.v + B.v - f[A.dl] - f[B.dl] + f[A.dl + B.dl];
  }
  for (int i = (1); i <= (q); ++i) printf("%d\n", 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 <class T>
inline bool getmin(T *a, const T &b) {
  if (b < *a) {
    *a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool getmax(T *a, const T &b) {
  if (b > *a) {
    *a = b;
    return true;
  }
  return false;
}
template <class T>
inline void read(T *a) {
  char c;
  while (isspace(c = getchar())) {
  }
  bool flag = 0;
  if (c == '-')
    flag = 1, *a = 0;
  else
    *a = c - 48;
  while (isdigit(c = getchar())) *a = *a * 10 + c - 48;
  if (flag) *a = -*a;
}
const int mo = 1000000007;
template <class T>
T pow(T a, T b, int c = mo) {
  T res = 1;
  for (T i = 1; i <= b; i <<= 1, a = 1LL * a * a % c)
    if (b & i) res = 1LL * res * a % c;
  return res;
}
const int N = 210000;
int f[N];
int n, q;
struct node {
  int v, dl, dr, size;
} tree[N * 2];
int dfn[N], id[N], idx;
struct edge_node {
  int p, nextt, w;
} edge[N];
pair<int, int> e[N];
int head[N];
int cnt;
void ae(int a, int b, int c) {
  edge[++cnt].p = b;
  edge[cnt].w = c;
  edge[cnt].nextt = head[a];
  head[a] = cnt;
}
int dep[N], size[N];
void getsize(int u, int fa) {
  size[u] = 1;
  for (int k = head[(u)]; k; k = edge[k].nextt) {
    int v = edge[k].p;
    if (v != fa) {
      getsize(v, u);
      size[u] += size[v];
    }
  }
}
int top[N], tot, g[N];
const int inf = 1000000001;
void dfs(int u, int fa, int r, int x) {
  dfn[u] = ++idx;
  if (x != inf) e[++tot] = std::make_pair(x, idx);
  g[u] = fa;
  id[idx] = u;
  top[u] = r;
  dep[u] = dep[fa] + 1;
  int e = 0;
  for (int k = head[(u)]; k; k = edge[k].nextt) {
    int v = edge[k].p;
    if (v != fa && size[v] > size[edge[e].p]) e = k;
  }
  if (e) dfs(edge[e].p, u, r, edge[e].w);
  for (int k = head[(u)]; k; k = edge[k].nextt) {
    int v = edge[k].p;
    if (v != fa && k != e) {
      dfs(v, u, v, edge[k].w);
    }
  }
}
void update(node &A, const node &X, const node &Y) {
  A.v = X.v + Y.v - f[X.dr] - f[Y.dl] + f[X.dr + Y.dl];
  A.dl = X.dl;
  if (X.dl == X.size) A.dl += Y.dl;
  A.dr = Y.dr;
  if (Y.dr == Y.size) A.dr += X.dr;
  A.size = X.size + Y.size;
}
void add(int u, int L, int R, int p) {
  if (L == R) {
    tree[u].v = f[1];
    tree[u].dl = tree[u].dr = 1;
    return;
  }
  int mid = (L + R) >> 1;
  if (p <= mid)
    add(u * 2, L, mid, p);
  else
    add(u * 2 + 1, mid + 1, R, p);
  update(tree[u], tree[u * 2], tree[u * 2 + 1]);
}
node query(int u, int L, int R, int l, int r) {
  if (l <= L && r >= R) return tree[u];
  int mid = (L + R) >> 1;
  if (r <= mid)
    return query(u * 2, L, mid, l, r);
  else if (l > mid)
    return query(u * 2 + 1, mid + 1, R, l, r);
  else {
    node ans;
    update(ans, query(u * 2, L, mid, l, mid),
           query(u * 2 + 1, mid + 1, R, mid + 1, r));
    return ans;
  }
}
int lca(int a, int b) {
  while (top[a] != top[b]) {
    if (dep[top[a]] > dep[top[b]])
      a = g[top[a]];
    else
      b = g[top[b]];
  }
  return dep[a] < dep[b] ? a : b;
}
struct Qnode {
  int x, y, w, p;
} Q[N];
bool cmp(const Qnode &A, const Qnode &B) { return A.w < B.w; }
int ans[N];
void build(int u, int L, int R) {
  tree[u].size = R - L + 1;
  if (L == R) return;
  int mid = (L + R) >> 1;
  build(u * 2, L, mid);
  build(u * 2 + 1, mid + 1, R);
}
node ask(int a, int b) {
  node res;
  res.v = res.dl = res.dr = 0;
  res.size = 0;
  while (dep[a] > dep[b]) {
    node xx = res;
    if (dep[top[a]] > dep[top[b]])
      update(res, query(1, 1, n, dfn[top[a]], dfn[a]), xx);
    else
      update(res, query(1, 1, n, dfn[b] + 1, dfn[a]), xx);
    a = g[top[a]];
  }
  return res;
}
int main() {
  cin >> n >> q;
  for (int i = (1); i <= (n - 1); ++i) read(f + i);
  for (int i = (2); i <= (n); ++i) {
    int x, y, z;
    read(&x);
    read(&y);
    read(&z);
    ae(x, y, z);
    ae(y, x, z);
  }
  getsize(1, 0);
  dfs(1, 0, 1, inf);
  build(1, 1, n);
  sort(e + 1, e + n);
  for (int i = (1); i <= (q); ++i) {
    read(&Q[i].x);
    read(&Q[i].y);
    read(&Q[i].w);
    Q[i].p = i;
  }
  sort(Q + 1, Q + q + 1, cmp);
  int j = n - 1;
  for (int i = (q); i >= (1); --i) {
    while (j >= 1 && e[j].first >= Q[i].w) add(1, 1, n, e[j].second), --j;
    int x = Q[i].x, y = Q[i].y, z = lca(x, y);
    node A = ask(x, z), B = ask(y, z);
    ans[Q[i].p] = A.v + B.v - f[A.dl] - f[B.dl] + f[A.dl + B.dl];
  }
  for (int i = (1); i <= (q); ++i) printf("%d\n", ans[i]);
  return 0;
}

```