#include <bits/stdc++.h>
using namespace std;
const int N = 111111;
int n, q, f[N];
struct node {
  bool e;
  int l, r, s;
  node(int x = 0) { e = x, l = x, r = x, s = 0; }
  int ans() {
    if (e) return f[l];
    return s + f[l] + f[r];
  }
} t[1 << 19], em;
node rev(node a) {
  swap(a.l, a.r);
  return a;
}
node operator+(node a, node b) {
  node c;
  c.e = a.e & b.e;
  c.l = a.l + a.e * b.l;
  c.r = b.r + b.e * a.r;
  c.s = a.s + b.s;
  if (!a.e && !b.e) c.s += f[a.r + b.l];
  return c;
}
void build(int k = 1, int l = 1, int r = n) {
  if (l == r) {
    t[k] = node(0);
    return;
  }
  int h = l + r >> 1;
  build(k << 1, l, h);
  build(k << 1 | 1, h + 1, r);
  t[k] = t[k << 1] + t[k << 1 | 1];
}
void modify(int x, int k = 1, int l = 1, int r = n) {
  if (l == r) {
    t[k] = node(1);
    return;
  }
  int h = l + r >> 1;
  if (x <= h)
    modify(x, k << 1, l, h);
  else
    modify(x, k << 1 | 1, h + 1, r);
  t[k] = t[k << 1] + t[k << 1 | 1];
}
node query(int L, int R, int k = 1, int l = 1, int r = n) {
  if (L > R) return em;
  if (L <= l && r <= R) return t[k];
  int h = l + r >> 1;
  node o = em;
  if (L <= h) o = o + query(L, R, k << 1, l, h);
  if (h < R) o = o + query(L, R, k << 1 | 1, h + 1, r);
  return o;
}
int a[N], b[N], c[N], d[N], e[N], tt, p[N];
vector<int> v[N], h[N], v1[N], v2[N];
void dfs1(int u, int fa) {
  int i, x;
  a[u] = fa;
  b[u] = 1;
  d[u] = d[fa] + 1;
  for (i = v[u].size(); i--;) {
    x = v[u][i];
    if (x == fa) continue;
    v1[h[u][i]].push_back(x);
    dfs1(x, u);
    b[u] += b[x];
    if (b[x] > b[c[u]]) c[u] = x;
  }
}
void dfs2(int u, int fa, int w) {
  int i, x;
  p[u] = ++tt;
  e[u] = w;
  if (c[u]) dfs2(c[u], u, e[u]);
  for (i = v[u].size(); i--;) {
    x = v[u][i];
    if (x == fa || x == c[u]) continue;
    dfs2(x, u, x);
  }
}
int m, w[N];
int qx[N], qy[N], qs[N];
int lb(int x) { return lower_bound(w, w + m, x) - w; }
node qu(int x, int y) {
  if (e[x] == e[y]) {
    if (d[x] < d[y]) return query(p[x] + 1, p[y]);
    return rev(query(p[y] + 1, p[x]));
  } else {
    if (d[e[x]] < d[e[y]]) return qu(x, a[e[y]]) + query(p[e[y]], p[y]);
    return rev(qu(y, a[e[x]]) + query(p[e[x]], p[x]));
  }
}
int main() {
  em.e = 1;
  int i, j, x, y, z;
  scanf("%d%d", &n, &q);
  for (i = 1; i < n; i = i + 1) scanf("%d", f + i);
  for (i = 1; i < n; i = i + 1) {
    scanf("%d%d%d", &x, &y, &z);
    w[m++] = z;
    v[x].push_back(y);
    h[x].push_back(z);
    v[y].push_back(x);
    h[y].push_back(z);
  }
  sort(w, w + m);
  m = unique(w, w + m) - w;
  for (i = 1; i <= n; i = i + 1)
    for (j = v[i].size(); j--;) h[i][j] = lb(h[i][j]);
  dfs1(1, 0);
  dfs2(1, 0, 1);
  build();
  for (i = 1; i <= q; i = i + 1) {
    scanf("%d%d%d", qx + i, qy + i, &z);
    v2[lb(z)].push_back(i);
  }
  for (i = m; i >= 0; i = i - 1) {
    for (j = v1[i].size(); j--;) modify(p[v1[i][j]]);
    for (j = v2[i].size(); j--;) {
      z = v2[i][j];
      qs[z] = qu(qx[z], qy[z]).ans();
    }
  }
  for (i = 1; i <= q; i = i + 1) cout << qs[i] << endl;
  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;
const int N = 111111;
int n, q, f[N];
struct node {
  bool e;
  int l, r, s;
  node(int x = 0) { e = x, l = x, r = x, s = 0; }
  int ans() {
    if (e) return f[l];
    return s + f[l] + f[r];
  }
} t[1 << 19], em;
node rev(node a) {
  swap(a.l, a.r);
  return a;
}
node operator+(node a, node b) {
  node c;
  c.e = a.e & b.e;
  c.l = a.l + a.e * b.l;
  c.r = b.r + b.e * a.r;
  c.s = a.s + b.s;
  if (!a.e && !b.e) c.s += f[a.r + b.l];
  return c;
}
void build(int k = 1, int l = 1, int r = n) {
  if (l == r) {
    t[k] = node(0);
    return;
  }
  int h = l + r >> 1;
  build(k << 1, l, h);
  build(k << 1 | 1, h + 1, r);
  t[k] = t[k << 1] + t[k << 1 | 1];
}
void modify(int x, int k = 1, int l = 1, int r = n) {
  if (l == r) {
    t[k] = node(1);
    return;
  }
  int h = l + r >> 1;
  if (x <= h)
    modify(x, k << 1, l, h);
  else
    modify(x, k << 1 | 1, h + 1, r);
  t[k] = t[k << 1] + t[k << 1 | 1];
}
node query(int L, int R, int k = 1, int l = 1, int r = n) {
  if (L > R) return em;
  if (L <= l && r <= R) return t[k];
  int h = l + r >> 1;
  node o = em;
  if (L <= h) o = o + query(L, R, k << 1, l, h);
  if (h < R) o = o + query(L, R, k << 1 | 1, h + 1, r);
  return o;
}
int a[N], b[N], c[N], d[N], e[N], tt, p[N];
vector<int> v[N], h[N], v1[N], v2[N];
void dfs1(int u, int fa) {
  int i, x;
  a[u] = fa;
  b[u] = 1;
  d[u] = d[fa] + 1;
  for (i = v[u].size(); i--;) {
    x = v[u][i];
    if (x == fa) continue;
    v1[h[u][i]].push_back(x);
    dfs1(x, u);
    b[u] += b[x];
    if (b[x] > b[c[u]]) c[u] = x;
  }
}
void dfs2(int u, int fa, int w) {
  int i, x;
  p[u] = ++tt;
  e[u] = w;
  if (c[u]) dfs2(c[u], u, e[u]);
  for (i = v[u].size(); i--;) {
    x = v[u][i];
    if (x == fa || x == c[u]) continue;
    dfs2(x, u, x);
  }
}
int m, w[N];
int qx[N], qy[N], qs[N];
int lb(int x) { return lower_bound(w, w + m, x) - w; }
node qu(int x, int y) {
  if (e[x] == e[y]) {
    if (d[x] < d[y]) return query(p[x] + 1, p[y]);
    return rev(query(p[y] + 1, p[x]));
  } else {
    if (d[e[x]] < d[e[y]]) return qu(x, a[e[y]]) + query(p[e[y]], p[y]);
    return rev(qu(y, a[e[x]]) + query(p[e[x]], p[x]));
  }
}
int main() {
  em.e = 1;
  int i, j, x, y, z;
  scanf("%d%d", &n, &q);
  for (i = 1; i < n; i = i + 1) scanf("%d", f + i);
  for (i = 1; i < n; i = i + 1) {
    scanf("%d%d%d", &x, &y, &z);
    w[m++] = z;
    v[x].push_back(y);
    h[x].push_back(z);
    v[y].push_back(x);
    h[y].push_back(z);
  }
  sort(w, w + m);
  m = unique(w, w + m) - w;
  for (i = 1; i <= n; i = i + 1)
    for (j = v[i].size(); j--;) h[i][j] = lb(h[i][j]);
  dfs1(1, 0);
  dfs2(1, 0, 1);
  build();
  for (i = 1; i <= q; i = i + 1) {
    scanf("%d%d%d", qx + i, qy + i, &z);
    v2[lb(z)].push_back(i);
  }
  for (i = m; i >= 0; i = i - 1) {
    for (j = v1[i].size(); j--;) modify(p[v1[i][j]]);
    for (j = v2[i].size(); j--;) {
      z = v2[i][j];
      qs[z] = qu(qx[z], qy[z]).ans();
    }
  }
  for (i = 1; i <= q; i = i + 1) cout << qs[i] << endl;
  return 0;
}

```