#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int INF = 1e9;
const int LOG = 18;
vector<int> ed[N];
vector<pair<pair<int, int>, pair<int, int> > > ep;
int n, q, tim, f[N], ans[N], sum[N], head[N], st[N], dad[N][LOG], dep[N];
struct node {
  int sum, pre, suff, siz;
  node() { sum = pre = suff = siz = 0; }
} tree[N << 2];
node merge(node l, node r) {
  node res;
  res.pre = l.pre + (l.pre == l.siz) * r.pre;
  res.suff = r.suff + (r.suff == r.siz) * l.suff;
  res.sum = l.sum + r.sum - f[l.suff] - f[r.pre] + f[l.suff + r.pre];
  res.siz = l.siz + r.siz;
  return res;
}
void update(int ind, int l, int r, int w) {
  if (l > w || r < w) return;
  if (l == w && r == w) {
    tree[ind].pre = tree[ind].suff = 1;
    tree[ind].sum = f[1];
    return;
  }
  int mid = (l + r) / 2;
  update(ind + ind, l, mid, w);
  update(ind + ind + 1, mid + 1, r, w);
  tree[ind] = merge(tree[ind + ind], tree[ind + ind + 1]);
}
node query(int ind, int l, int r, int lw, int rw) {
  if (l > rw || r < lw) return node();
  if (l >= lw && r <= rw) return tree[ind];
  int mid = (l + r) / 2;
  return merge(query(ind + ind, l, mid, lw, rw),
               query(ind + ind + 1, mid + 1, r, lw, rw));
}
void init(int ind, int l, int r) {
  if (l == r) {
    tree[ind].siz = 1;
    return;
  }
  int mid = (l + r) / 2;
  init(ind + ind, l, mid);
  init(ind + ind + 1, mid + 1, r);
  tree[ind] = merge(tree[ind + ind], tree[ind + ind + 1]);
}
int get_lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = LOG - 1; i >= 0; i--)
    if (dep[dad[x][i]] >= dep[y]) x = dad[x][i];
  if (x == y) return x;
  for (int i = LOG - 1; i >= 0; i--)
    if (dad[x][i] != dad[y][i]) x = dad[x][i], y = dad[y][i];
  return dad[x][0];
}
void add(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  update(1, 1, n, st[u]);
}
int get(int u, int v) {
  node t1, t2;
  int lca = get_lca(u, v);
  int asd = 0;
  while (u != lca) {
    if (dep[head[u]] <= dep[lca]) {
      t1 = merge(query(1, 1, n, st[lca] + 1, st[u]), t1);
      break;
    }
    t1 = merge(query(1, 1, n, st[head[u]], st[u]), t1);
    u = dad[head[u]][0];
  }
  while (v != lca) {
    if (dep[head[v]] <= dep[lca]) {
      t2 = merge(query(1, 1, n, st[lca] + 1, st[v]), t2);
      break;
    }
    t2 = merge(query(1, 1, n, st[head[v]], st[v]), t2);
    v = dad[head[v]][0];
  }
  swap(t1.pre, t1.suff);
  return merge(t1, t2).sum;
}
int dfs(int cur, int back) {
  dep[cur] = dep[back] + 1;
  dad[cur][0] = back;
  for (int i = 1; i < LOG; i++) dad[cur][i] = dad[dad[cur][i - 1]][i - 1];
  sum[cur] = 1;
  for (auto i : ed[cur])
    if (i != back) sum[cur] += dfs(i, cur);
  return sum[cur];
}
void dfs2(int cur, int back, int curhead) {
  head[cur] = curhead;
  st[cur] = ++tim;
  int go = 0;
  for (auto i : ed[cur])
    if (i != back && sum[go] <= sum[i]) go = i;
  if (go != 0) dfs2(go, cur, curhead);
  for (auto i : ed[cur])
    if (i != back && i != go) dfs2(i, cur, i);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> q;
  for (int i = 1; i < n; i++) cin >> f[i];
  for (int i = 1; i < n; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    ed[u].push_back(v);
    ed[v].push_back(u);
    ep.push_back({{c, INF}, {u, v}});
  }
  for (int i = 1; i <= q; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    ep.push_back({{c, i}, {u, v}});
  }
  dfs(1, 0);
  dfs2(1, 0, 1);
  for (int i = 1; i <= n; i++) {
    int x = i;
    while (x != 1 && x != 0) x = dad[head[x]][0];
  }
  sort(ep.begin(), ep.end());
  reverse(ep.begin(), ep.end());
  init(1, 1, n);
  for (auto i : ep) {
    int typ = i.first.second, u = i.second.first, v = i.second.second;
    if (typ == INF)
      add(u, v);
    else
      ans[typ] = get(u, v);
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

### Prompt

Generate 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;
const int N = 1e5 + 5;
const int INF = 1e9;
const int LOG = 18;
vector<int> ed[N];
vector<pair<pair<int, int>, pair<int, int> > > ep;
int n, q, tim, f[N], ans[N], sum[N], head[N], st[N], dad[N][LOG], dep[N];
struct node {
  int sum, pre, suff, siz;
  node() { sum = pre = suff = siz = 0; }
} tree[N << 2];
node merge(node l, node r) {
  node res;
  res.pre = l.pre + (l.pre == l.siz) * r.pre;
  res.suff = r.suff + (r.suff == r.siz) * l.suff;
  res.sum = l.sum + r.sum - f[l.suff] - f[r.pre] + f[l.suff + r.pre];
  res.siz = l.siz + r.siz;
  return res;
}
void update(int ind, int l, int r, int w) {
  if (l > w || r < w) return;
  if (l == w && r == w) {
    tree[ind].pre = tree[ind].suff = 1;
    tree[ind].sum = f[1];
    return;
  }
  int mid = (l + r) / 2;
  update(ind + ind, l, mid, w);
  update(ind + ind + 1, mid + 1, r, w);
  tree[ind] = merge(tree[ind + ind], tree[ind + ind + 1]);
}
node query(int ind, int l, int r, int lw, int rw) {
  if (l > rw || r < lw) return node();
  if (l >= lw && r <= rw) return tree[ind];
  int mid = (l + r) / 2;
  return merge(query(ind + ind, l, mid, lw, rw),
               query(ind + ind + 1, mid + 1, r, lw, rw));
}
void init(int ind, int l, int r) {
  if (l == r) {
    tree[ind].siz = 1;
    return;
  }
  int mid = (l + r) / 2;
  init(ind + ind, l, mid);
  init(ind + ind + 1, mid + 1, r);
  tree[ind] = merge(tree[ind + ind], tree[ind + ind + 1]);
}
int get_lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = LOG - 1; i >= 0; i--)
    if (dep[dad[x][i]] >= dep[y]) x = dad[x][i];
  if (x == y) return x;
  for (int i = LOG - 1; i >= 0; i--)
    if (dad[x][i] != dad[y][i]) x = dad[x][i], y = dad[y][i];
  return dad[x][0];
}
void add(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  update(1, 1, n, st[u]);
}
int get(int u, int v) {
  node t1, t2;
  int lca = get_lca(u, v);
  int asd = 0;
  while (u != lca) {
    if (dep[head[u]] <= dep[lca]) {
      t1 = merge(query(1, 1, n, st[lca] + 1, st[u]), t1);
      break;
    }
    t1 = merge(query(1, 1, n, st[head[u]], st[u]), t1);
    u = dad[head[u]][0];
  }
  while (v != lca) {
    if (dep[head[v]] <= dep[lca]) {
      t2 = merge(query(1, 1, n, st[lca] + 1, st[v]), t2);
      break;
    }
    t2 = merge(query(1, 1, n, st[head[v]], st[v]), t2);
    v = dad[head[v]][0];
  }
  swap(t1.pre, t1.suff);
  return merge(t1, t2).sum;
}
int dfs(int cur, int back) {
  dep[cur] = dep[back] + 1;
  dad[cur][0] = back;
  for (int i = 1; i < LOG; i++) dad[cur][i] = dad[dad[cur][i - 1]][i - 1];
  sum[cur] = 1;
  for (auto i : ed[cur])
    if (i != back) sum[cur] += dfs(i, cur);
  return sum[cur];
}
void dfs2(int cur, int back, int curhead) {
  head[cur] = curhead;
  st[cur] = ++tim;
  int go = 0;
  for (auto i : ed[cur])
    if (i != back && sum[go] <= sum[i]) go = i;
  if (go != 0) dfs2(go, cur, curhead);
  for (auto i : ed[cur])
    if (i != back && i != go) dfs2(i, cur, i);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> q;
  for (int i = 1; i < n; i++) cin >> f[i];
  for (int i = 1; i < n; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    ed[u].push_back(v);
    ed[v].push_back(u);
    ep.push_back({{c, INF}, {u, v}});
  }
  for (int i = 1; i <= q; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    ep.push_back({{c, i}, {u, v}});
  }
  dfs(1, 0);
  dfs2(1, 0, 1);
  for (int i = 1; i <= n; i++) {
    int x = i;
    while (x != 1 && x != 0) x = dad[head[x]][0];
  }
  sort(ep.begin(), ep.end());
  reverse(ep.begin(), ep.end());
  init(1, 1, n);
  for (auto i : ep) {
    int typ = i.first.second, u = i.second.first, v = i.second.second;
    if (typ == INF)
      add(u, v);
    else
      ans[typ] = get(u, v);
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

```