#include <bits/stdc++.h>
using namespace std;
struct node {
  int len, lf, rf, insum;
};
struct jff {
  int cs, tp, u, v;
};
node tr[2000000], k1, k2;
vector<pair<int, int> > ed[200000];
int d[200000], n, m;
vector<int> sp[2000000];
int hg[200000], up[200000][19], kl, frst, x, y, z, we[200000], parent[200000],
    zn[200000], sl[200000], lght[200000], t, sz[200000], v;
jff qr[300000];
void add_new(int z, int x, int y, int t) {
  kl++;
  qr[kl] = (jff){z, t, x, y};
}
node compare(node k1, node k2) {
  node k3 = (node){0, 0, 0, 0};
  k3.insum = k1.insum + k2.insum;
  if (k1.rf != k1.len && k2.len != k2.lf) k3.insum += d[k1.rf + k2.lf];
  k3.lf = k1.lf;
  k3.rf = k2.rf;
  if (k1.lf == k1.len) k3.lf += k2.lf;
  if (k2.rf == k2.len) k3.rf += k1.rf;
  k3.len = k1.len + k2.len;
  return k3;
}
void md(int x, int l, int r, int ll, int y) {
  if (l == r) {
    tr[x] = (node){1, y, y, 0};
    return;
  }
  int mid = (r + l) / 2;
  if (ll <= mid) md(x * 2, l, mid, ll, y);
  if (ll > mid) md(x * 2 + 1, mid + 1, r, ll, y);
  tr[x] = compare(tr[x * 2], tr[x * 2 + 1]);
}
void find_ans(int x, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) {
    k1 = compare(tr[x], k1);
    return;
  }
  int mid = (r + l) / 2;
  if (rr > mid) find_ans(x * 2 + 1, mid + 1, r, ll, rr);
  if (ll <= mid) find_ans(x * 2, l, mid, ll, rr);
}
void dfs1(int x, int h, int pr) {
  hg[x] = h;
  parent[x] = pr;
  up[x][0] = pr;
  sz[x] = 1;
  for (int j = 1; j <= 17; j++) up[x][j] = up[up[x][j - 1]][j - 1];
  for (int i = 0; i < ed[x].size(); i++) {
    int to = ed[x][i].first;
    int cs = ed[x][i].second;
    if (to == pr) continue;
    dfs1(to, h + 1, x);
    sz[x] += sz[to];
  }
}
void dfs2(int x, int y) {
  if (y == 1) v++;
  sp[v].push_back(x);
  int mx = 0, nm;
  for (int i = 0; i < ed[x].size(); i++) {
    int to = ed[x][i].first;
    int cs = ed[x][i].second;
    if (to == parent[x]) continue;
    if (sz[to] > mx) {
      mx = sz[to];
      nm = to;
    }
  }
  if (sz[x] == 1) return;
  t++;
  sl[nm] = t;
  zn[nm] = 1;
  md(1, 1, n, t, 1);
  lght[nm] = v;
  dfs2(nm, 0);
  for (int i = 0; i < ed[x].size(); i++) {
    int to = ed[x][i].first;
    int cs = ed[x][i].second;
    if (to == parent[x]) continue;
    if (to == nm) continue;
    zn[to] = 1;
    dfs2(to, 1);
  }
}
int find_lca(int x, int y) {
  if (hg[x] > hg[y]) swap(x, y);
  for (int j = 17; j >= 0; j--)
    if (hg[up[y][j]] >= hg[x]) y = up[y][j];
  for (int j = 17; j >= 0; j--) {
    int xn = up[x][j];
    int yn = up[y][j];
    if (xn == 0) continue;
    if (xn != yn) {
      x = xn;
      y = yn;
      continue;
    }
  }
  if (x == y) return x;
  if (parent[x] != parent[y]) exit(0);
  return parent[x];
}
void goupper(int lca, int y) {
  k1 = (node){0, 0, 0, 0};
  while (y != lca) {
    if (lght[y] == 0) {
      k1 = compare((node){1, zn[y], zn[y], 0}, k1);
      y = parent[y];
    } else {
      int vr = sp[lght[y]][0];
      int ll, rr;
      rr = sl[y];
      if (hg[vr] > hg[lca])
        ll = sl[sp[lght[y]][1]];
      else {
        int fst = sl[sp[lght[y]][1]];
        ll = fst + (hg[lca] - hg[vr]);
        find_ans(1, 1, n, ll, rr);
        break;
      }
      find_ans(1, 1, n, ll, rr);
      y = vr;
    }
  }
}
bool CMP(const jff &i, const jff &j) {
  return (i.cs < j.cs || (i.cs == j.cs && i.tp < j.tp));
}
int main() {
  hg[0] = -1;
  ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n - 1; i++) scanf("%d", &d[i]);
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d%d%d", &x, &y, &z);
    ed[x].push_back(make_pair(y, z));
    ed[y].push_back(make_pair(x, z));
    add_new(z, x, y, m + 1);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &x, &y, &z);
    add_new(z, x, y, i);
  }
  sort(qr + 1, qr + kl + 1, CMP);
  dfs1(1, 0, 0);
  dfs2(1, 1);
  for (int i = 1; i <= kl; i++) {
    if (qr[i].tp == m + 1) {
      int x = qr[i].u;
      int y = qr[i].v;
      if (hg[x] > hg[y]) swap(x, y);
      zn[y] = 0;
      if (lght[y] != 0) md(1, 1, n, sl[y], 0);
    } else {
      int x = qr[i].u;
      int y = qr[i].v;
      if (hg[x] > hg[y]) swap(x, y);
      int lca = find_lca(x, y);
      int ans = 0;
      if (x == lca) {
        goupper(lca, y);
        if (k1.lf == k1.len)
          ans = d[k1.len];
        else
          ans = k1.insum + d[k1.lf] + d[k1.rf];
      } else {
        goupper(lca, y);
        k2 = k1;
        goupper(lca, x);
        swap(k1.lf, k1.rf);
        k1 = compare(k1, k2);
        if (k1.len == k1.lf)
          ans = d[k1.len];
        else
          ans = k1.insum + d[k1.lf] + d[k1.rf];
      }
      we[qr[i].tp] = ans;
    }
  }
  for (int i = 1; i <= m; i++) printf("%d\n", we[i]);
  return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

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 node {
  int len, lf, rf, insum;
};
struct jff {
  int cs, tp, u, v;
};
node tr[2000000], k1, k2;
vector<pair<int, int> > ed[200000];
int d[200000], n, m;
vector<int> sp[2000000];
int hg[200000], up[200000][19], kl, frst, x, y, z, we[200000], parent[200000],
    zn[200000], sl[200000], lght[200000], t, sz[200000], v;
jff qr[300000];
void add_new(int z, int x, int y, int t) {
  kl++;
  qr[kl] = (jff){z, t, x, y};
}
node compare(node k1, node k2) {
  node k3 = (node){0, 0, 0, 0};
  k3.insum = k1.insum + k2.insum;
  if (k1.rf != k1.len && k2.len != k2.lf) k3.insum += d[k1.rf + k2.lf];
  k3.lf = k1.lf;
  k3.rf = k2.rf;
  if (k1.lf == k1.len) k3.lf += k2.lf;
  if (k2.rf == k2.len) k3.rf += k1.rf;
  k3.len = k1.len + k2.len;
  return k3;
}
void md(int x, int l, int r, int ll, int y) {
  if (l == r) {
    tr[x] = (node){1, y, y, 0};
    return;
  }
  int mid = (r + l) / 2;
  if (ll <= mid) md(x * 2, l, mid, ll, y);
  if (ll > mid) md(x * 2 + 1, mid + 1, r, ll, y);
  tr[x] = compare(tr[x * 2], tr[x * 2 + 1]);
}
void find_ans(int x, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) {
    k1 = compare(tr[x], k1);
    return;
  }
  int mid = (r + l) / 2;
  if (rr > mid) find_ans(x * 2 + 1, mid + 1, r, ll, rr);
  if (ll <= mid) find_ans(x * 2, l, mid, ll, rr);
}
void dfs1(int x, int h, int pr) {
  hg[x] = h;
  parent[x] = pr;
  up[x][0] = pr;
  sz[x] = 1;
  for (int j = 1; j <= 17; j++) up[x][j] = up[up[x][j - 1]][j - 1];
  for (int i = 0; i < ed[x].size(); i++) {
    int to = ed[x][i].first;
    int cs = ed[x][i].second;
    if (to == pr) continue;
    dfs1(to, h + 1, x);
    sz[x] += sz[to];
  }
}
void dfs2(int x, int y) {
  if (y == 1) v++;
  sp[v].push_back(x);
  int mx = 0, nm;
  for (int i = 0; i < ed[x].size(); i++) {
    int to = ed[x][i].first;
    int cs = ed[x][i].second;
    if (to == parent[x]) continue;
    if (sz[to] > mx) {
      mx = sz[to];
      nm = to;
    }
  }
  if (sz[x] == 1) return;
  t++;
  sl[nm] = t;
  zn[nm] = 1;
  md(1, 1, n, t, 1);
  lght[nm] = v;
  dfs2(nm, 0);
  for (int i = 0; i < ed[x].size(); i++) {
    int to = ed[x][i].first;
    int cs = ed[x][i].second;
    if (to == parent[x]) continue;
    if (to == nm) continue;
    zn[to] = 1;
    dfs2(to, 1);
  }
}
int find_lca(int x, int y) {
  if (hg[x] > hg[y]) swap(x, y);
  for (int j = 17; j >= 0; j--)
    if (hg[up[y][j]] >= hg[x]) y = up[y][j];
  for (int j = 17; j >= 0; j--) {
    int xn = up[x][j];
    int yn = up[y][j];
    if (xn == 0) continue;
    if (xn != yn) {
      x = xn;
      y = yn;
      continue;
    }
  }
  if (x == y) return x;
  if (parent[x] != parent[y]) exit(0);
  return parent[x];
}
void goupper(int lca, int y) {
  k1 = (node){0, 0, 0, 0};
  while (y != lca) {
    if (lght[y] == 0) {
      k1 = compare((node){1, zn[y], zn[y], 0}, k1);
      y = parent[y];
    } else {
      int vr = sp[lght[y]][0];
      int ll, rr;
      rr = sl[y];
      if (hg[vr] > hg[lca])
        ll = sl[sp[lght[y]][1]];
      else {
        int fst = sl[sp[lght[y]][1]];
        ll = fst + (hg[lca] - hg[vr]);
        find_ans(1, 1, n, ll, rr);
        break;
      }
      find_ans(1, 1, n, ll, rr);
      y = vr;
    }
  }
}
bool CMP(const jff &i, const jff &j) {
  return (i.cs < j.cs || (i.cs == j.cs && i.tp < j.tp));
}
int main() {
  hg[0] = -1;
  ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n - 1; i++) scanf("%d", &d[i]);
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d%d%d", &x, &y, &z);
    ed[x].push_back(make_pair(y, z));
    ed[y].push_back(make_pair(x, z));
    add_new(z, x, y, m + 1);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &x, &y, &z);
    add_new(z, x, y, i);
  }
  sort(qr + 1, qr + kl + 1, CMP);
  dfs1(1, 0, 0);
  dfs2(1, 1);
  for (int i = 1; i <= kl; i++) {
    if (qr[i].tp == m + 1) {
      int x = qr[i].u;
      int y = qr[i].v;
      if (hg[x] > hg[y]) swap(x, y);
      zn[y] = 0;
      if (lght[y] != 0) md(1, 1, n, sl[y], 0);
    } else {
      int x = qr[i].u;
      int y = qr[i].v;
      if (hg[x] > hg[y]) swap(x, y);
      int lca = find_lca(x, y);
      int ans = 0;
      if (x == lca) {
        goupper(lca, y);
        if (k1.lf == k1.len)
          ans = d[k1.len];
        else
          ans = k1.insum + d[k1.lf] + d[k1.rf];
      } else {
        goupper(lca, y);
        k2 = k1;
        goupper(lca, x);
        swap(k1.lf, k1.rf);
        k1 = compare(k1, k2);
        if (k1.len == k1.lf)
          ans = d[k1.len];
        else
          ans = k1.insum + d[k1.lf] + d[k1.rf];
      }
      we[qr[i].tp] = ans;
    }
  }
  for (int i = 1; i <= m; i++) printf("%d\n", we[i]);
  return 0;
}

```