#include <bits/stdc++.h>
using namespace std;
int n, q, f[100005], h[100005], p[100005][18], sz[100005], spe[100005];
int pos[100005], beg[100005], belong[100005], num = 0, rig = 0;
vector<int> g[100005];
pair<int, pair<pair<int, int>, int> > que[100005];
pair<int, pair<int, int> > e[100005];
long long ans[100005];
struct node {
  long long sum;
  int lef, rig, sz;
  node() { sum = lef = rig = sz = 0; }
  node(long long _sum, int _lef, int _rig, int _sz) {
    sum = _sum;
    lef = _lef;
    rig = _rig;
    sz = _sz;
  }
};
node com(node a, node b) {
  node re;
  re.sz = a.sz + b.sz;
  if (a.lef == a.sz)
    re.lef = a.lef + b.lef;
  else
    re.lef = a.lef;
  if (b.rig == b.sz)
    re.rig = b.rig + a.rig;
  else
    re.rig = b.rig;
  re.sum = a.sum + b.sum - f[a.rig] - f[b.lef] + f[a.rig + b.lef];
  return re;
}
struct interval {
  node tree[100005 << 2];
  void build(int l, int r, int id) {
    if (l == r) {
      tree[id] = node(0, 0, 0, 1);
      return;
    }
    int g = ((l + r) >> 1);
    build(l, g, id << 1);
    build(g + 1, r, (id << 1) + 1);
    tree[id] = com(tree[id << 1], tree[(id << 1) + 1]);
  }
  void update(int l, int r, int id, int x) {
    if (l > x || r < x) return;
    if (l == r) {
      tree[id] = node(f[1], 1, 1, 1);
      return;
    }
    int g = ((l + r) >> 1);
    update(l, g, id << 1, x);
    update(g + 1, r, (id << 1) + 1, x);
    tree[id] = com(tree[id << 1], tree[(id << 1) + 1]);
  }
  node get(int l, int r, int id, int x, int y) {
    if (l > y || r < x) return node();
    if (x <= l && r <= y) return tree[id];
    int g = ((l + r) >> 1);
    node a = get(l, g, id << 1, x, y);
    node b = get(g + 1, r, (id << 1) + 1, x, y);
    return com(a, b);
  }
} t;
void setup() {
  cin >> n >> q;
  for (int i = 1; i <= n - 1; i++) cin >> f[i];
  for (int i = 1; i <= n - 1; i++) {
    cin >> e[i].second.first >> e[i].second.second >> e[i].first;
    g[e[i].second.first].push_back(e[i].second.second);
    g[e[i].second.second].push_back(e[i].second.first);
  }
  for (int i = 1; i <= q; i++) {
    cin >> que[i].second.first.first >> que[i].second.first.second >>
        que[i].first;
    que[i].second.second = i;
  }
  sort(e + 1, e + n);
  sort(que + 1, que + q + 1);
  t.build(2, n, 1);
}
void dfs(int u) {
  sz[u] = 1;
  for (int i = 0; i <= int(g[u].size()) - 1; i++) {
    int v = g[u][i];
    if (v == p[u][0]) continue;
    p[v][0] = u;
    for (int i = 1; i <= 17; i++) p[v][i] = p[p[v][i - 1]][i - 1];
    h[v] = h[u] + 1;
    dfs(v);
    if (sz[v] > sz[spe[u]]) spe[u] = v;
    sz[u] += sz[v];
  }
}
void hld(int u) {
  if (beg[num] == 0) beg[num] = u;
  belong[u] = num;
  pos[u] = ++rig;
  if (spe[u]) {
    hld(spe[u]);
    for (int i = 0; i <= int(g[u].size()) - 1; i++) {
      int v = g[u][i];
      if (v == p[u][0] || v == spe[u]) continue;
      num++;
      hld(v);
    }
  }
}
int lca(int a, int b) {
  if (h[a] > h[b]) swap(a, b);
  int dif = h[b] - h[a];
  for (int i = 0; i <= 17; i++)
    if ((dif >> i) & 1) b = p[b][i];
  if (a == b) return a;
  for (int i = 17; i >= 0; i--)
    if (p[a][i] != p[b][i]) {
      a = p[a][i];
      b = p[b][i];
    }
  return p[a][0];
}
node get(int a, int b) {
  node re = node();
  while (belong[a] != belong[b]) {
    re = com(t.get(2, n, 1, pos[beg[belong[a]]], pos[a]), re);
    a = p[beg[belong[a]]][0];
  }
  re = com(t.get(2, n, 1, pos[b] + 1, pos[a]), re);
  return re;
}
void xuly() {
  dfs(1);
  hld(1);
  int top = n;
  for (int i = q; i >= 1; i--) {
    int u = que[i].second.first.first;
    int v = que[i].second.first.second;
    int l = lca(u, v);
    while (top > 1 && e[top - 1].first >= que[i].first) {
      top--;
      if (h[e[top].second.first] > h[e[top].second.second])
        swap(e[top].second.first, e[top].second.second);
      t.update(2, n, 1, pos[e[top].second.second]);
    }
    node a, b, c;
    if (h[u] > h[l])
      a = get(u, l);
    else
      a = node();
    if (h[v] > h[l])
      b = get(v, l);
    else
      b = node();
    swap(a.lef, a.rig);
    c = com(a, b);
    ans[que[i].second.second] = c.sum;
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  setup();
  xuly();
  return 0;
}

### Prompt

Your challenge is to write a CPP solution 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;
int n, q, f[100005], h[100005], p[100005][18], sz[100005], spe[100005];
int pos[100005], beg[100005], belong[100005], num = 0, rig = 0;
vector<int> g[100005];
pair<int, pair<pair<int, int>, int> > que[100005];
pair<int, pair<int, int> > e[100005];
long long ans[100005];
struct node {
  long long sum;
  int lef, rig, sz;
  node() { sum = lef = rig = sz = 0; }
  node(long long _sum, int _lef, int _rig, int _sz) {
    sum = _sum;
    lef = _lef;
    rig = _rig;
    sz = _sz;
  }
};
node com(node a, node b) {
  node re;
  re.sz = a.sz + b.sz;
  if (a.lef == a.sz)
    re.lef = a.lef + b.lef;
  else
    re.lef = a.lef;
  if (b.rig == b.sz)
    re.rig = b.rig + a.rig;
  else
    re.rig = b.rig;
  re.sum = a.sum + b.sum - f[a.rig] - f[b.lef] + f[a.rig + b.lef];
  return re;
}
struct interval {
  node tree[100005 << 2];
  void build(int l, int r, int id) {
    if (l == r) {
      tree[id] = node(0, 0, 0, 1);
      return;
    }
    int g = ((l + r) >> 1);
    build(l, g, id << 1);
    build(g + 1, r, (id << 1) + 1);
    tree[id] = com(tree[id << 1], tree[(id << 1) + 1]);
  }
  void update(int l, int r, int id, int x) {
    if (l > x || r < x) return;
    if (l == r) {
      tree[id] = node(f[1], 1, 1, 1);
      return;
    }
    int g = ((l + r) >> 1);
    update(l, g, id << 1, x);
    update(g + 1, r, (id << 1) + 1, x);
    tree[id] = com(tree[id << 1], tree[(id << 1) + 1]);
  }
  node get(int l, int r, int id, int x, int y) {
    if (l > y || r < x) return node();
    if (x <= l && r <= y) return tree[id];
    int g = ((l + r) >> 1);
    node a = get(l, g, id << 1, x, y);
    node b = get(g + 1, r, (id << 1) + 1, x, y);
    return com(a, b);
  }
} t;
void setup() {
  cin >> n >> q;
  for (int i = 1; i <= n - 1; i++) cin >> f[i];
  for (int i = 1; i <= n - 1; i++) {
    cin >> e[i].second.first >> e[i].second.second >> e[i].first;
    g[e[i].second.first].push_back(e[i].second.second);
    g[e[i].second.second].push_back(e[i].second.first);
  }
  for (int i = 1; i <= q; i++) {
    cin >> que[i].second.first.first >> que[i].second.first.second >>
        que[i].first;
    que[i].second.second = i;
  }
  sort(e + 1, e + n);
  sort(que + 1, que + q + 1);
  t.build(2, n, 1);
}
void dfs(int u) {
  sz[u] = 1;
  for (int i = 0; i <= int(g[u].size()) - 1; i++) {
    int v = g[u][i];
    if (v == p[u][0]) continue;
    p[v][0] = u;
    for (int i = 1; i <= 17; i++) p[v][i] = p[p[v][i - 1]][i - 1];
    h[v] = h[u] + 1;
    dfs(v);
    if (sz[v] > sz[spe[u]]) spe[u] = v;
    sz[u] += sz[v];
  }
}
void hld(int u) {
  if (beg[num] == 0) beg[num] = u;
  belong[u] = num;
  pos[u] = ++rig;
  if (spe[u]) {
    hld(spe[u]);
    for (int i = 0; i <= int(g[u].size()) - 1; i++) {
      int v = g[u][i];
      if (v == p[u][0] || v == spe[u]) continue;
      num++;
      hld(v);
    }
  }
}
int lca(int a, int b) {
  if (h[a] > h[b]) swap(a, b);
  int dif = h[b] - h[a];
  for (int i = 0; i <= 17; i++)
    if ((dif >> i) & 1) b = p[b][i];
  if (a == b) return a;
  for (int i = 17; i >= 0; i--)
    if (p[a][i] != p[b][i]) {
      a = p[a][i];
      b = p[b][i];
    }
  return p[a][0];
}
node get(int a, int b) {
  node re = node();
  while (belong[a] != belong[b]) {
    re = com(t.get(2, n, 1, pos[beg[belong[a]]], pos[a]), re);
    a = p[beg[belong[a]]][0];
  }
  re = com(t.get(2, n, 1, pos[b] + 1, pos[a]), re);
  return re;
}
void xuly() {
  dfs(1);
  hld(1);
  int top = n;
  for (int i = q; i >= 1; i--) {
    int u = que[i].second.first.first;
    int v = que[i].second.first.second;
    int l = lca(u, v);
    while (top > 1 && e[top - 1].first >= que[i].first) {
      top--;
      if (h[e[top].second.first] > h[e[top].second.second])
        swap(e[top].second.first, e[top].second.second);
      t.update(2, n, 1, pos[e[top].second.second]);
    }
    node a, b, c;
    if (h[u] > h[l])
      a = get(u, l);
    else
      a = node();
    if (h[v] > h[l])
      b = get(v, l);
    else
      b = node();
    swap(a.lef, a.rig);
    c = com(a, b);
    ans[que[i].second.second] = c.sum;
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  setup();
  xuly();
  return 0;
}

```