#include <bits/stdc++.h>
using namespace std;
struct Info {
  int lmax, rmax, sum, len;
  Info() { lmax = rmax = sum = len = -1; }
};
int ans[505050], f[550500];
Info operator+(const Info &a, const Info &b) {
  Info c;
  if (a.len == -1) {
    return b;
  }
  if (b.len == -1) {
    return a;
  }
  if (a.rmax == 0 || b.lmax == 0) {
    c.lmax = a.lmax;
    c.rmax = b.rmax;
    c.sum = a.sum + b.sum;
    c.len = a.len + b.len;
    return c;
  }
  c.sum = a.sum + b.sum;
  c.sum -= f[a.rmax];
  c.sum -= f[b.lmax];
  c.lmax = a.lmax;
  if (a.lmax == a.len) {
    c.lmax += b.lmax;
  }
  c.rmax = b.rmax;
  if (b.rmax == b.len) {
    c.rmax += a.rmax;
  }
  c.sum += f[a.rmax + b.lmax];
  c.len = a.len + b.len;
  if (c.lmax + c.rmax == c.len) {
    c.lmax = c.rmax = c.len;
  }
  return c;
}
struct SegT {
  int l, r, lc, rc;
  Info info;
} tree[500005];
int segpos[500005], dep[500005], now[500005], val[500005];
int son[500005], pre[500005], last[500005], len[500005], tot;
int belong[500005], father[500005], size[500005], root[500005];
vector<pair<int, int> > p;
struct Query {
  int x, y, w, id;
} query[505055];
bool com(Query a, Query b) { return a.w < b.w; }
void add(int a, int b, int c) {
  son[++tot] = b;
  len[tot] = c;
  pre[tot] = last[a];
  last[a] = tot;
}
void maketree(int l, int r) {
  tree[tot].l = l;
  tree[tot].r = r;
  if (l == r) {
    tree[tot].info.sum = f[1];
    tree[tot].info.lmax = 1;
    tree[tot].info.rmax = 1;
    tree[tot].info.len = 1;
    return;
  }
  int mid = (l + r) >> 1;
  int k = tot;
  tree[k].lc = ++tot;
  maketree(l, mid);
  tree[k].rc = ++tot;
  maketree(mid + 1, r);
  tree[k].info = tree[tree[k].lc].info + tree[tree[k].rc].info;
}
void change(int rt, int pos) {
  if (tree[rt].l == tree[rt].r) {
    tree[rt].info.sum = 0;
    tree[rt].info.lmax = tree[rt].info.rmax = 0;
    return;
  }
  int mid = (tree[rt].l + tree[rt].r) >> 1;
  if (pos <= mid) {
    change(tree[rt].lc, pos);
  } else {
    change(tree[rt].rc, pos);
  }
  tree[rt].info = tree[tree[rt].lc].info + tree[tree[rt].rc].info;
}
Info findsum(int rt, int a, int b) {
  Info res;
  if (a > b) {
    return res;
  }
  if (tree[rt].l >= a && tree[rt].r <= b) {
    return tree[rt].info;
  }
  int mid = (tree[rt].l + tree[rt].r) >> 1;
  if (a <= mid) {
    res = res + findsum(tree[rt].lc, a, b);
  }
  if (b > mid) {
    res = res + findsum(tree[rt].rc, a, b);
  }
  return res;
}
void dfs(int k) {
  size[k] = 1;
  int Max = 0, maxn = -1;
  for (int x = last[k]; x; x = pre[x]) {
    if (son[x] != father[k]) {
      father[son[x]] = k;
      dep[son[x]] = dep[k] + 1;
      dfs(son[x]);
      p.push_back(make_pair(len[x], son[x]));
      size[k] += size[son[x]];
      if (size[son[x]] > Max) {
        Max = size[son[x]];
        maxn = son[x];
      }
    }
  }
  if (maxn != -1) {
    belong[maxn] = 1;
  }
}
void build(int k) {
  if (belong[k]) {
    belong[k] = belong[father[k]];
  } else {
    belong[k] = k;
  }
  int flag = 0;
  for (int x = last[k]; x; x = pre[x]) {
    if (son[x] != father[k]) {
      build(son[x]);
      flag = 1;
    }
  }
  if (!flag) {
    int cnt = 0, i;
    for (i = k; i != belong[i]; i = father[i]) {
      segpos[i] = ++cnt;
      now[cnt] = i;
    }
    segpos[i] = ++cnt;
    now[cnt] = i;
    root[belong[i]] = ++tot;
    maketree(1, cnt);
  }
}
Info findans(int a, int b) {
  Info infoA, infoB;
  while (belong[a] != belong[b]) {
    if (dep[belong[a]] > dep[belong[b]]) {
      infoA = infoA + findsum(root[belong[a]], segpos[a], segpos[belong[a]]);
      a = father[belong[a]];
    } else {
      infoB = infoB + findsum(root[belong[b]], segpos[b], segpos[belong[b]]);
      b = father[belong[b]];
    }
  }
  int ordA = segpos[a], ordB = segpos[b];
  int left = min(ordA, ordB);
  int Right = max(ordA, ordB);
  Info info = findsum(root[belong[a]], left, Right - 1);
  if (ordA == left) {
    infoA = infoA + info;
  } else {
    infoB = infoB + info;
  }
  swap(infoB.lmax, infoB.rmax);
  return infoA + infoB;
}
int main() {
  int n, q;
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    scanf("%d", &f[i]);
  }
  for (int i = 1; i < n; i++) {
    int x, y, w;
    scanf("%d %d %d", &x, &y, &w);
    add(x, y, w);
    add(y, x, w);
  }
  for (int i = 1; i <= q; i++) {
    scanf("%d %d %d", &query[i].x, &query[i].y, &query[i].w);
    query[i].id = i;
  }
  sort(query + 1, query + 1 + q, com);
  dfs(1);
  tot = 0;
  build(1);
  sort(p.begin(), p.end());
  for (int i = 1, cur = 0; i <= q; i++) {
    while (cur < (int)p.size() && p[cur].first < query[i].w) {
      change(root[belong[p[cur].second]], segpos[p[cur].second]);
      cur++;
    }
    ans[query[i].id] = findans(query[i].x, query[i].y).sum;
  }
  for (int i = 1; i <= q; i++) {
    printf("%d\n", ans[i]);
  }
  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 namespace std;
struct Info {
  int lmax, rmax, sum, len;
  Info() { lmax = rmax = sum = len = -1; }
};
int ans[505050], f[550500];
Info operator+(const Info &a, const Info &b) {
  Info c;
  if (a.len == -1) {
    return b;
  }
  if (b.len == -1) {
    return a;
  }
  if (a.rmax == 0 || b.lmax == 0) {
    c.lmax = a.lmax;
    c.rmax = b.rmax;
    c.sum = a.sum + b.sum;
    c.len = a.len + b.len;
    return c;
  }
  c.sum = a.sum + b.sum;
  c.sum -= f[a.rmax];
  c.sum -= f[b.lmax];
  c.lmax = a.lmax;
  if (a.lmax == a.len) {
    c.lmax += b.lmax;
  }
  c.rmax = b.rmax;
  if (b.rmax == b.len) {
    c.rmax += a.rmax;
  }
  c.sum += f[a.rmax + b.lmax];
  c.len = a.len + b.len;
  if (c.lmax + c.rmax == c.len) {
    c.lmax = c.rmax = c.len;
  }
  return c;
}
struct SegT {
  int l, r, lc, rc;
  Info info;
} tree[500005];
int segpos[500005], dep[500005], now[500005], val[500005];
int son[500005], pre[500005], last[500005], len[500005], tot;
int belong[500005], father[500005], size[500005], root[500005];
vector<pair<int, int> > p;
struct Query {
  int x, y, w, id;
} query[505055];
bool com(Query a, Query b) { return a.w < b.w; }
void add(int a, int b, int c) {
  son[++tot] = b;
  len[tot] = c;
  pre[tot] = last[a];
  last[a] = tot;
}
void maketree(int l, int r) {
  tree[tot].l = l;
  tree[tot].r = r;
  if (l == r) {
    tree[tot].info.sum = f[1];
    tree[tot].info.lmax = 1;
    tree[tot].info.rmax = 1;
    tree[tot].info.len = 1;
    return;
  }
  int mid = (l + r) >> 1;
  int k = tot;
  tree[k].lc = ++tot;
  maketree(l, mid);
  tree[k].rc = ++tot;
  maketree(mid + 1, r);
  tree[k].info = tree[tree[k].lc].info + tree[tree[k].rc].info;
}
void change(int rt, int pos) {
  if (tree[rt].l == tree[rt].r) {
    tree[rt].info.sum = 0;
    tree[rt].info.lmax = tree[rt].info.rmax = 0;
    return;
  }
  int mid = (tree[rt].l + tree[rt].r) >> 1;
  if (pos <= mid) {
    change(tree[rt].lc, pos);
  } else {
    change(tree[rt].rc, pos);
  }
  tree[rt].info = tree[tree[rt].lc].info + tree[tree[rt].rc].info;
}
Info findsum(int rt, int a, int b) {
  Info res;
  if (a > b) {
    return res;
  }
  if (tree[rt].l >= a && tree[rt].r <= b) {
    return tree[rt].info;
  }
  int mid = (tree[rt].l + tree[rt].r) >> 1;
  if (a <= mid) {
    res = res + findsum(tree[rt].lc, a, b);
  }
  if (b > mid) {
    res = res + findsum(tree[rt].rc, a, b);
  }
  return res;
}
void dfs(int k) {
  size[k] = 1;
  int Max = 0, maxn = -1;
  for (int x = last[k]; x; x = pre[x]) {
    if (son[x] != father[k]) {
      father[son[x]] = k;
      dep[son[x]] = dep[k] + 1;
      dfs(son[x]);
      p.push_back(make_pair(len[x], son[x]));
      size[k] += size[son[x]];
      if (size[son[x]] > Max) {
        Max = size[son[x]];
        maxn = son[x];
      }
    }
  }
  if (maxn != -1) {
    belong[maxn] = 1;
  }
}
void build(int k) {
  if (belong[k]) {
    belong[k] = belong[father[k]];
  } else {
    belong[k] = k;
  }
  int flag = 0;
  for (int x = last[k]; x; x = pre[x]) {
    if (son[x] != father[k]) {
      build(son[x]);
      flag = 1;
    }
  }
  if (!flag) {
    int cnt = 0, i;
    for (i = k; i != belong[i]; i = father[i]) {
      segpos[i] = ++cnt;
      now[cnt] = i;
    }
    segpos[i] = ++cnt;
    now[cnt] = i;
    root[belong[i]] = ++tot;
    maketree(1, cnt);
  }
}
Info findans(int a, int b) {
  Info infoA, infoB;
  while (belong[a] != belong[b]) {
    if (dep[belong[a]] > dep[belong[b]]) {
      infoA = infoA + findsum(root[belong[a]], segpos[a], segpos[belong[a]]);
      a = father[belong[a]];
    } else {
      infoB = infoB + findsum(root[belong[b]], segpos[b], segpos[belong[b]]);
      b = father[belong[b]];
    }
  }
  int ordA = segpos[a], ordB = segpos[b];
  int left = min(ordA, ordB);
  int Right = max(ordA, ordB);
  Info info = findsum(root[belong[a]], left, Right - 1);
  if (ordA == left) {
    infoA = infoA + info;
  } else {
    infoB = infoB + info;
  }
  swap(infoB.lmax, infoB.rmax);
  return infoA + infoB;
}
int main() {
  int n, q;
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    scanf("%d", &f[i]);
  }
  for (int i = 1; i < n; i++) {
    int x, y, w;
    scanf("%d %d %d", &x, &y, &w);
    add(x, y, w);
    add(y, x, w);
  }
  for (int i = 1; i <= q; i++) {
    scanf("%d %d %d", &query[i].x, &query[i].y, &query[i].w);
    query[i].id = i;
  }
  sort(query + 1, query + 1 + q, com);
  dfs(1);
  tot = 0;
  build(1);
  sort(p.begin(), p.end());
  for (int i = 1, cur = 0; i <= q; i++) {
    while (cur < (int)p.size() && p[cur].first < query[i].w) {
      change(root[belong[p[cur].second]], segpos[p[cur].second]);
      cur++;
    }
    ans[query[i].id] = findans(query[i].x, query[i].y).sum;
  }
  for (int i = 1; i <= q; i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}

```