#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10, MAXLG = 17;
int F[MAXN];
struct node {
  int stat;
  int lsiz, rsiz;
  int sum;
  int size;
};
void print(node n, const char *name = "node") {
  printf("%s: stat = %d, lsiz = %d, rsiz = %d, sum = %d, size = %d\n", name,
         n.stat, n.lsiz, n.rsiz, n.sum, n.size);
}
node getstat(int sz, int x) {
  node res;
  res.size = sz;
  res.stat = x;
  res.sum = 0;
  if (x == 0) {
    res.lsiz = res.rsiz = 0;
  } else if (x == 2) {
    res.lsiz = res.rsiz = sz;
  } else {
    assert(!"Invalid stat");
  }
  return res;
}
node ZERO, ONE = getstat(1, 2);
int eval(node n) {
  if (n.stat == 0) {
    return 0;
  } else if (n.stat == 2) {
    return F[n.size];
  } else {
    return n.sum + F[n.lsiz] + F[n.rsiz];
  }
}
node operator+(node n1, node n2) {
  if (n1.size == 0) {
    return n2;
  }
  if (n2.size == 0) {
    return n1;
  }
  node res;
  if (n1.stat == n2.stat && (n1.stat == 0 || n1.stat == 2)) {
    res.stat = n1.stat;
  } else {
    res.stat = 1;
  }
  res.lsiz = n1.lsiz;
  if (n1.lsiz == n1.size) {
    res.lsiz += n2.lsiz;
  }
  res.rsiz = n2.rsiz;
  if (n2.rsiz == n2.size) {
    res.rsiz += n1.rsiz;
  }
  res.size = n1.size + n2.size;
  if (n1.stat == 0) {
    if (n2.stat == 0) {
      res.sum = 0;
    } else if (n2.stat == 1) {
      res.sum = F[n2.lsiz] + n2.sum;
    } else {
      res.sum = 0;
    }
  } else if (n1.stat == 1) {
    if (n2.stat == 0) {
      res.sum = n1.sum + F[n1.rsiz];
    } else if (n2.stat == 1) {
      res.sum = n1.sum + F[n1.rsiz + n2.lsiz] + n2.sum;
    } else {
      res.sum = n1.sum;
    }
  } else {
    if (n2.stat == 0) {
      res.sum = 0;
    } else if (n2.stat == 1) {
      res.sum = n2.sum;
    } else {
      res.sum = 0;
    }
  }
  return res;
}
int N, M;
map<pair<int, int>, int> mpw;
int wp[MAXN];
pair<int, pair<int, int> > E[MAXN];
pair<pair<int, int>, pair<int, int> > Q[MAXN];
vector<int> adj[MAXN];
struct chain {
  vector<node> tree;
  vector<int> nodes;
  vector<int> leaf;
  int size;
  chain() : tree(), nodes(), size() {}
  void init() {
    int sz = size = nodes.size();
    tree.resize(4 * sz);
    leaf.resize(sz);
    build(1, 0, sz);
  }
  void build(int cur, int lt, int rt) {
    tree[cur] = getstat(rt - lt, 0);
    if (rt - lt == 1) {
      leaf[lt] = cur;
    } else {
      int mid = (lt + rt) / 2;
      build(2 * cur, lt, mid);
      build(2 * cur + 1, mid, rt);
    }
  }
  node query(int a, int b, int cur, int lt, int rt) {
    if (rt <= a || b <= lt) {
      return ZERO;
    }
    if (a <= lt && rt <= b) {
      return tree[cur];
    }
    int mid = (lt + rt) / 2;
    return query(a, b, 2 * cur, lt, mid) + query(a, b, 2 * cur + 1, mid, rt);
  }
  node query(int a, int b) { return query(a, b, 1, 0, size); }
  void update(int x) {
    for (tree[x = leaf[x]] = ONE; x /= 2;) {
      tree[x] = tree[2 * x] + tree[2 * x + 1];
    }
  }
};
int C = 1;
chain ch[MAXN];
int chbel[MAXN], chind[MAXN];
int par[MAXN][MAXLG], depth[MAXN], sub[MAXN];
int dfs1(int x, int p, int d) {
  par[x][0] = p;
  depth[x] = d;
  wp[x] = mpw[pair<int, int>(x, p)];
  int res = 1;
  for (int t : adj[x]) {
    if (t != p) {
      res += dfs1(t, x, d + 1);
    }
  }
  return sub[x] = res;
}
int getpar(int x, int d) {
  for (int i = 0; d; d /= 2, i++) {
    if (d & 1) {
      x = par[x][i];
    }
  }
  return x;
}
int lca(int x, int y) {
  if (depth[x] > depth[y]) {
    swap(x, y);
  }
  y = getpar(y, depth[y] - depth[x]);
  if (x == y) {
    return x;
  }
  for (int k = MAXLG - 1; k >= 0; k--) {
    if (par[x][k] != par[y][k]) {
      x = par[x][k];
      y = par[y][k];
    }
  }
  return par[x][0];
}
void dfs2(int x, int chid) {
  chbel[x] = chid;
  chind[x] = ch[chid].nodes.size();
  ch[chid].nodes.push_back(x);
  for (int t : adj[x]) {
    if (t == par[x][0]) {
      continue;
    }
    if (sub[t] * 2 >= sub[x]) {
      dfs2(t, chid);
    } else {
      dfs2(t, ++C);
    }
  }
}
node go(int x, int c) {
  c = getpar(x, depth[x] - depth[c] - 1);
  node ans = ZERO;
  while (true) {
    int b = chbel[x];
    int xind = chind[x];
    int ltind = (b == chbel[c] ? chind[c] : 0);
    ans = ch[b].query(ltind, xind + 1) + ans;
    if (b == chbel[c]) {
      break;
    }
    x = par[ch[b].nodes[0]][0];
  }
  return ans;
}
int ans[MAXN];
void test() {
  node n1;
  n1.stat = 1;
  n1.lsiz = 1;
  n1.rsiz = 1;
  n1.sum = 0;
  n1.size = 3;
  node n2;
  n2 = n1;
  node sum = n1 + n2;
  print(sum, "sum");
  exit(0);
}
int main() {
  if (fopen("input.txt", "r")) {
    freopen("input.txt", "r", stdin);
  }
  scanf("%d %d", &N, &M);
  for (int i = 1; i < N; i++) {
    scanf("%d", &F[i]);
  }
  for (int i = 1, a, b, w; i < N; i++) {
    scanf("%d %d %d", &a, &b, &w);
    adj[a].push_back(b);
    adj[b].push_back(a);
    E[i] = make_pair(w, pair<int, int>(a, b));
    mpw[pair<int, int>(a, b)] = mpw[pair<int, int>(b, a)] = w;
  }
  sort(E + 1, E + N);
  reverse(E + 1, E + N);
  dfs1(1, 0, 0);
  for (int j = 1; j < MAXLG; j++) {
    for (int i = 1; i <= N; i++) {
      par[i][j] = par[par[i][j - 1]][j - 1];
    }
  }
  dfs2(1, 1);
  for (int c = 1; c <= C; c++) {
    ch[c].init();
  }
  for (int i = 1; i <= M; i++) {
    scanf("%d %d %d", &Q[i].second.first, &Q[i].second.second,
          &Q[i].first.first);
    Q[i].first.second = i;
  }
  sort(Q + 1, Q + M + 1);
  reverse(Q + 1, Q + M + 1);
  for (int i = 1; i < N; i++) {
    int &a = E[i].second.first, &b = E[i].second.second;
    if (depth[a] > depth[b]) {
      swap(a, b);
    }
  }
  for (int i = 1, j = 1; i <= M; i++) {
    int w = Q[i].first.first, a = Q[i].second.first, b = Q[i].second.second;
    if (depth[a] < depth[b]) {
      swap(a, b);
    }
    int c = lca(a, b);
    for (; j < N && E[j].first >= w; j++) {
      int x = E[j].second.second;
      ch[chbel[x]].update(chind[x]);
    }
    node n = go(a, c);
    if (b != c) {
      node n2 = go(b, c);
      swap(n2.lsiz, n2.rsiz);
      n = n2 + n;
    }
    ans[Q[i].first.second] = eval(n);
  }
  for (int i = 1; i <= M; i++) {
    printf("%d\n", ans[i]);
  }
}

### Prompt

Please formulate 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 MAXN = 1e5 + 10, MAXLG = 17;
int F[MAXN];
struct node {
  int stat;
  int lsiz, rsiz;
  int sum;
  int size;
};
void print(node n, const char *name = "node") {
  printf("%s: stat = %d, lsiz = %d, rsiz = %d, sum = %d, size = %d\n", name,
         n.stat, n.lsiz, n.rsiz, n.sum, n.size);
}
node getstat(int sz, int x) {
  node res;
  res.size = sz;
  res.stat = x;
  res.sum = 0;
  if (x == 0) {
    res.lsiz = res.rsiz = 0;
  } else if (x == 2) {
    res.lsiz = res.rsiz = sz;
  } else {
    assert(!"Invalid stat");
  }
  return res;
}
node ZERO, ONE = getstat(1, 2);
int eval(node n) {
  if (n.stat == 0) {
    return 0;
  } else if (n.stat == 2) {
    return F[n.size];
  } else {
    return n.sum + F[n.lsiz] + F[n.rsiz];
  }
}
node operator+(node n1, node n2) {
  if (n1.size == 0) {
    return n2;
  }
  if (n2.size == 0) {
    return n1;
  }
  node res;
  if (n1.stat == n2.stat && (n1.stat == 0 || n1.stat == 2)) {
    res.stat = n1.stat;
  } else {
    res.stat = 1;
  }
  res.lsiz = n1.lsiz;
  if (n1.lsiz == n1.size) {
    res.lsiz += n2.lsiz;
  }
  res.rsiz = n2.rsiz;
  if (n2.rsiz == n2.size) {
    res.rsiz += n1.rsiz;
  }
  res.size = n1.size + n2.size;
  if (n1.stat == 0) {
    if (n2.stat == 0) {
      res.sum = 0;
    } else if (n2.stat == 1) {
      res.sum = F[n2.lsiz] + n2.sum;
    } else {
      res.sum = 0;
    }
  } else if (n1.stat == 1) {
    if (n2.stat == 0) {
      res.sum = n1.sum + F[n1.rsiz];
    } else if (n2.stat == 1) {
      res.sum = n1.sum + F[n1.rsiz + n2.lsiz] + n2.sum;
    } else {
      res.sum = n1.sum;
    }
  } else {
    if (n2.stat == 0) {
      res.sum = 0;
    } else if (n2.stat == 1) {
      res.sum = n2.sum;
    } else {
      res.sum = 0;
    }
  }
  return res;
}
int N, M;
map<pair<int, int>, int> mpw;
int wp[MAXN];
pair<int, pair<int, int> > E[MAXN];
pair<pair<int, int>, pair<int, int> > Q[MAXN];
vector<int> adj[MAXN];
struct chain {
  vector<node> tree;
  vector<int> nodes;
  vector<int> leaf;
  int size;
  chain() : tree(), nodes(), size() {}
  void init() {
    int sz = size = nodes.size();
    tree.resize(4 * sz);
    leaf.resize(sz);
    build(1, 0, sz);
  }
  void build(int cur, int lt, int rt) {
    tree[cur] = getstat(rt - lt, 0);
    if (rt - lt == 1) {
      leaf[lt] = cur;
    } else {
      int mid = (lt + rt) / 2;
      build(2 * cur, lt, mid);
      build(2 * cur + 1, mid, rt);
    }
  }
  node query(int a, int b, int cur, int lt, int rt) {
    if (rt <= a || b <= lt) {
      return ZERO;
    }
    if (a <= lt && rt <= b) {
      return tree[cur];
    }
    int mid = (lt + rt) / 2;
    return query(a, b, 2 * cur, lt, mid) + query(a, b, 2 * cur + 1, mid, rt);
  }
  node query(int a, int b) { return query(a, b, 1, 0, size); }
  void update(int x) {
    for (tree[x = leaf[x]] = ONE; x /= 2;) {
      tree[x] = tree[2 * x] + tree[2 * x + 1];
    }
  }
};
int C = 1;
chain ch[MAXN];
int chbel[MAXN], chind[MAXN];
int par[MAXN][MAXLG], depth[MAXN], sub[MAXN];
int dfs1(int x, int p, int d) {
  par[x][0] = p;
  depth[x] = d;
  wp[x] = mpw[pair<int, int>(x, p)];
  int res = 1;
  for (int t : adj[x]) {
    if (t != p) {
      res += dfs1(t, x, d + 1);
    }
  }
  return sub[x] = res;
}
int getpar(int x, int d) {
  for (int i = 0; d; d /= 2, i++) {
    if (d & 1) {
      x = par[x][i];
    }
  }
  return x;
}
int lca(int x, int y) {
  if (depth[x] > depth[y]) {
    swap(x, y);
  }
  y = getpar(y, depth[y] - depth[x]);
  if (x == y) {
    return x;
  }
  for (int k = MAXLG - 1; k >= 0; k--) {
    if (par[x][k] != par[y][k]) {
      x = par[x][k];
      y = par[y][k];
    }
  }
  return par[x][0];
}
void dfs2(int x, int chid) {
  chbel[x] = chid;
  chind[x] = ch[chid].nodes.size();
  ch[chid].nodes.push_back(x);
  for (int t : adj[x]) {
    if (t == par[x][0]) {
      continue;
    }
    if (sub[t] * 2 >= sub[x]) {
      dfs2(t, chid);
    } else {
      dfs2(t, ++C);
    }
  }
}
node go(int x, int c) {
  c = getpar(x, depth[x] - depth[c] - 1);
  node ans = ZERO;
  while (true) {
    int b = chbel[x];
    int xind = chind[x];
    int ltind = (b == chbel[c] ? chind[c] : 0);
    ans = ch[b].query(ltind, xind + 1) + ans;
    if (b == chbel[c]) {
      break;
    }
    x = par[ch[b].nodes[0]][0];
  }
  return ans;
}
int ans[MAXN];
void test() {
  node n1;
  n1.stat = 1;
  n1.lsiz = 1;
  n1.rsiz = 1;
  n1.sum = 0;
  n1.size = 3;
  node n2;
  n2 = n1;
  node sum = n1 + n2;
  print(sum, "sum");
  exit(0);
}
int main() {
  if (fopen("input.txt", "r")) {
    freopen("input.txt", "r", stdin);
  }
  scanf("%d %d", &N, &M);
  for (int i = 1; i < N; i++) {
    scanf("%d", &F[i]);
  }
  for (int i = 1, a, b, w; i < N; i++) {
    scanf("%d %d %d", &a, &b, &w);
    adj[a].push_back(b);
    adj[b].push_back(a);
    E[i] = make_pair(w, pair<int, int>(a, b));
    mpw[pair<int, int>(a, b)] = mpw[pair<int, int>(b, a)] = w;
  }
  sort(E + 1, E + N);
  reverse(E + 1, E + N);
  dfs1(1, 0, 0);
  for (int j = 1; j < MAXLG; j++) {
    for (int i = 1; i <= N; i++) {
      par[i][j] = par[par[i][j - 1]][j - 1];
    }
  }
  dfs2(1, 1);
  for (int c = 1; c <= C; c++) {
    ch[c].init();
  }
  for (int i = 1; i <= M; i++) {
    scanf("%d %d %d", &Q[i].second.first, &Q[i].second.second,
          &Q[i].first.first);
    Q[i].first.second = i;
  }
  sort(Q + 1, Q + M + 1);
  reverse(Q + 1, Q + M + 1);
  for (int i = 1; i < N; i++) {
    int &a = E[i].second.first, &b = E[i].second.second;
    if (depth[a] > depth[b]) {
      swap(a, b);
    }
  }
  for (int i = 1, j = 1; i <= M; i++) {
    int w = Q[i].first.first, a = Q[i].second.first, b = Q[i].second.second;
    if (depth[a] < depth[b]) {
      swap(a, b);
    }
    int c = lca(a, b);
    for (; j < N && E[j].first >= w; j++) {
      int x = E[j].second.second;
      ch[chbel[x]].update(chind[x]);
    }
    node n = go(a, c);
    if (b != c) {
      node n2 = go(b, c);
      swap(n2.lsiz, n2.rsiz);
      n = n2 + n;
    }
    ans[Q[i].first.second] = eval(n);
  }
  for (int i = 1; i <= M; i++) {
    printf("%d\n", ans[i]);
  }
}

```