#include <bits/stdc++.h>
using std::cerr;
using std::make_pair;
using std::pair;
using std::swap;
using std::vector;
int f[100010];
class data {
 public:
  int len, lmx, rmx, sum;
  data operator+(const data &t) const {
    data ret;
    ret.len = len + t.len;
    ret.sum = sum + t.sum;
    ret.lmx = lmx;
    if (lmx == len) ret.lmx += t.lmx;
    ret.rmx = t.rmx;
    if (t.rmx == t.len) ret.rmx += rmx;
    if (rmx && t.lmx) ret.sum += -f[rmx] - f[t.lmx] + f[rmx + t.lmx];
    return ret;
  }
  data inverse() {
    data ret = *this;
    swap(ret.lmx, ret.rmx);
    return ret;
  }
};
class node {
 public:
  int ch[2];
  data dat;
} t[2200000];
int rt[100010];
int nodecnt = 0;
void build(int &p, int l, int r) {
  p = ++nodecnt;
  t[p].dat = (data){r - l + 1, 0, 0, 0};
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(t[p].ch[0], l, mid);
  build(t[p].ch[1], mid + 1, r);
}
void modify(int &p, int q, int l, int r, int pos) {
  p = ++nodecnt;
  t[p] = t[q];
  if (l == r) {
    t[p].dat = (data){1, 1, 1, f[1]};
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    modify(t[p].ch[0], t[q].ch[0], l, mid, pos);
  else
    modify(t[p].ch[1], t[q].ch[1], mid + 1, r, pos);
  t[p].dat = t[t[p].ch[0]].dat + t[t[p].ch[1]].dat;
}
void query(int p, int l, int r, int ql, int qr, data &ret) {
  if (ql <= l && r <= qr) {
    ret = ret + t[p].dat;
    return;
  }
  int mid = (l + r) >> 1;
  if (ql <= mid) query(t[p].ch[0], l, mid, ql, qr, ret);
  if (qr > mid) query(t[p].ch[1], mid + 1, r, ql, qr, ret);
}
vector<pair<int, int> > edg;
int fa[100010], dfn[100010], siz[100010], ch[100010], top[100010], tim,
    dep[100010];
vector<pair<int, int> > v[100010];
inline int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]])
      x = fa[top[x]];
    else
      y = fa[top[y]];
  }
  return dep[x] > dep[y] ? y : x;
}
void dfs1(int np, int fath) {
  siz[np] = 1;
  fa[np] = fath;
  dep[np] = dep[fath] + 1;
  for (int i = 0; i < v[np].size(); i++) {
    pair<int, int> x = v[np][i];
    if (x.first == fath) continue;
    dfs1(x.first, np);
    siz[np] += siz[x.first];
    if (!ch[np] || siz[x.first] > siz[ch[np]]) ch[np] = x.first;
  }
}
void dfs2(int np, int tp) {
  top[np] = tp;
  dfn[np] = ++tim;
  if (ch[np]) dfs2(ch[np], tp);
  for (int i = 0; i < v[np].size(); i++) {
    pair<int, int> x = v[np][i];
    if (x.first == fa[np]) continue;
    if (x.first == ch[np]) {
      edg.push_back(make_pair(x.second, dfn[x.first]));
      continue;
    }
    dfs2(x.first, x.first);
    edg.push_back(make_pair(x.second, dfn[x.first]));
  }
}
int n, m, ev[100010];
data getchain(int x, int y, int t) {
  data ret = (data){0, 0, 0};
  while (top[x] != top[y]) {
    data v = (data){0, 0, 0};
    query(t, 1, n, dfn[top[x]], dfn[x], v);
    x = fa[top[x]];
    ret = v + ret;
  }
  if (x != y) {
    data v = (data){0, 0, 0};
    query(t, 1, n, dfn[y] + 1, dfn[x], v);
    ret = v + ret;
  }
  return ret;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i < n; i++) scanf("%d", &f[i]);
  for (int i = 1, a, b, c; i < n; i++) {
    scanf("%d%d%d", &a, &b, &c);
    v[a].push_back(make_pair(b, c));
    v[b].push_back(make_pair(a, c));
  }
  dfs1(1, 0);
  dfs2(1, 1);
  sort(edg.begin(), edg.end());
  reverse(edg.begin(), edg.end());
  build(rt[0], 1, n);
  for (int i = 0; i < n - 1; i++) {
    ev[i + 1] = edg[i].first;
    modify(rt[i + 1], rt[i], 1, n, edg[i].second);
  }
  ev[0] = 0x3f3f3f3f;
  while (m--) {
    int x, y, l;
    scanf("%d%d%d", &x, &y, &l);
    int p = -1;
    int LL = 0, RR = n - 1;
    while (LL <= RR) {
      int mid = (LL + RR) >> 1;
      if (ev[mid] >= l)
        p = mid, LL = mid + 1;
      else
        RR = mid - 1;
    }
    int L = lca(x, y);
    data A = getchain(x, L, rt[p]), B = getchain(y, L, rt[p]);
    A = B.inverse() + A;
    printf("%d\n", A.sum);
  }
  return 0;
}

### Prompt

Please provide a Cpp coded solution 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 std::cerr;
using std::make_pair;
using std::pair;
using std::swap;
using std::vector;
int f[100010];
class data {
 public:
  int len, lmx, rmx, sum;
  data operator+(const data &t) const {
    data ret;
    ret.len = len + t.len;
    ret.sum = sum + t.sum;
    ret.lmx = lmx;
    if (lmx == len) ret.lmx += t.lmx;
    ret.rmx = t.rmx;
    if (t.rmx == t.len) ret.rmx += rmx;
    if (rmx && t.lmx) ret.sum += -f[rmx] - f[t.lmx] + f[rmx + t.lmx];
    return ret;
  }
  data inverse() {
    data ret = *this;
    swap(ret.lmx, ret.rmx);
    return ret;
  }
};
class node {
 public:
  int ch[2];
  data dat;
} t[2200000];
int rt[100010];
int nodecnt = 0;
void build(int &p, int l, int r) {
  p = ++nodecnt;
  t[p].dat = (data){r - l + 1, 0, 0, 0};
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(t[p].ch[0], l, mid);
  build(t[p].ch[1], mid + 1, r);
}
void modify(int &p, int q, int l, int r, int pos) {
  p = ++nodecnt;
  t[p] = t[q];
  if (l == r) {
    t[p].dat = (data){1, 1, 1, f[1]};
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    modify(t[p].ch[0], t[q].ch[0], l, mid, pos);
  else
    modify(t[p].ch[1], t[q].ch[1], mid + 1, r, pos);
  t[p].dat = t[t[p].ch[0]].dat + t[t[p].ch[1]].dat;
}
void query(int p, int l, int r, int ql, int qr, data &ret) {
  if (ql <= l && r <= qr) {
    ret = ret + t[p].dat;
    return;
  }
  int mid = (l + r) >> 1;
  if (ql <= mid) query(t[p].ch[0], l, mid, ql, qr, ret);
  if (qr > mid) query(t[p].ch[1], mid + 1, r, ql, qr, ret);
}
vector<pair<int, int> > edg;
int fa[100010], dfn[100010], siz[100010], ch[100010], top[100010], tim,
    dep[100010];
vector<pair<int, int> > v[100010];
inline int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]])
      x = fa[top[x]];
    else
      y = fa[top[y]];
  }
  return dep[x] > dep[y] ? y : x;
}
void dfs1(int np, int fath) {
  siz[np] = 1;
  fa[np] = fath;
  dep[np] = dep[fath] + 1;
  for (int i = 0; i < v[np].size(); i++) {
    pair<int, int> x = v[np][i];
    if (x.first == fath) continue;
    dfs1(x.first, np);
    siz[np] += siz[x.first];
    if (!ch[np] || siz[x.first] > siz[ch[np]]) ch[np] = x.first;
  }
}
void dfs2(int np, int tp) {
  top[np] = tp;
  dfn[np] = ++tim;
  if (ch[np]) dfs2(ch[np], tp);
  for (int i = 0; i < v[np].size(); i++) {
    pair<int, int> x = v[np][i];
    if (x.first == fa[np]) continue;
    if (x.first == ch[np]) {
      edg.push_back(make_pair(x.second, dfn[x.first]));
      continue;
    }
    dfs2(x.first, x.first);
    edg.push_back(make_pair(x.second, dfn[x.first]));
  }
}
int n, m, ev[100010];
data getchain(int x, int y, int t) {
  data ret = (data){0, 0, 0};
  while (top[x] != top[y]) {
    data v = (data){0, 0, 0};
    query(t, 1, n, dfn[top[x]], dfn[x], v);
    x = fa[top[x]];
    ret = v + ret;
  }
  if (x != y) {
    data v = (data){0, 0, 0};
    query(t, 1, n, dfn[y] + 1, dfn[x], v);
    ret = v + ret;
  }
  return ret;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i < n; i++) scanf("%d", &f[i]);
  for (int i = 1, a, b, c; i < n; i++) {
    scanf("%d%d%d", &a, &b, &c);
    v[a].push_back(make_pair(b, c));
    v[b].push_back(make_pair(a, c));
  }
  dfs1(1, 0);
  dfs2(1, 1);
  sort(edg.begin(), edg.end());
  reverse(edg.begin(), edg.end());
  build(rt[0], 1, n);
  for (int i = 0; i < n - 1; i++) {
    ev[i + 1] = edg[i].first;
    modify(rt[i + 1], rt[i], 1, n, edg[i].second);
  }
  ev[0] = 0x3f3f3f3f;
  while (m--) {
    int x, y, l;
    scanf("%d%d%d", &x, &y, &l);
    int p = -1;
    int LL = 0, RR = n - 1;
    while (LL <= RR) {
      int mid = (LL + RR) >> 1;
      if (ev[mid] >= l)
        p = mid, LL = mid + 1;
      else
        RR = mid - 1;
    }
    int L = lca(x, y);
    data A = getchain(x, L, rt[p]), B = getchain(y, L, rt[p]);
    A = B.inverse() + A;
    printf("%d\n", A.sum);
  }
  return 0;
}

```