#include <bits/stdc++.h>
using namespace std;
const double EPS = -1e8;
const double Pi = acos(-1);
bool inline equ(double a, double b) { return fabs(a - b) < EPS; }
const int MAXN = 100010;
const int LOG = 19;
struct HLD {
  int n;
  vector<int> g[MAXN];
  int sz[MAXN], dep[MAXN];
  int ts, tid[MAXN], tdi[MAXN], tl[MAXN], tr[MAXN];
  int mom[MAXN][LOG], head[MAXN];
  void dfssz(int u, int p) {
    dep[u] = dep[p] + 1;
    mom[u][0] = p;
    sz[u] = 1;
    head[u] = u;
    for (int& v : g[u])
      if (v != p) {
        dep[v] = dep[u] + 1;
        dfssz(v, u);
        sz[u] += sz[v];
      }
  }
  void dfshl(int u) {
    ts++;
    tid[u] = tl[u] = tr[u] = ts;
    tdi[tid[u]] = u;
    sort((g[u]).begin(), (g[u]).end(),
         [&](int a, int b) { return sz[a] > sz[b]; });
    bool flag = 1;
    for (int& v : g[u])
      if (v != mom[u][0]) {
        if (flag) head[v] = head[u], flag = 0;
        dfshl(v);
        tr[u] = tr[v];
      }
  }
  inline int lca(int a, int b) {
    if (dep[a] > dep[b]) swap(a, b);
    int diff = dep[b] - dep[a];
    for (int k = (LOG - 1); k >= (0); k--)
      if (diff & (1 << k)) {
        b = mom[b][k];
      }
    if (a == b) return a;
    for (int k = (LOG - 1); k >= (0); k--)
      if (mom[a][k] != mom[b][k]) {
        a = mom[a][k];
        b = mom[b][k];
      }
    return mom[a][0];
  }
  void init(int _n) {
    n = _n;
    for (int i = (1); i <= (n); i++) g[i].clear();
  }
  void addEdge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
  }
  void yutruli() {
    dfssz(1, 0);
    ts = 0;
    dfshl(1);
    for (int k = (1); k <= (LOG - 1); k++)
      for (int i = (1); i <= (n); i++) mom[i][k] = mom[mom[i][k - 1]][k - 1];
  }
  vector<tuple<int, int> > getPath(int u, int v) {
    vector<tuple<int, int> > res;
    while (tid[u] < tid[head[v]]) {
      res.push_back(tuple<int, int>(tid[head[v]], tid[v]));
      v = mom[head[v]][0];
    }
    res.push_back(tuple<int, int>(tid[u], tid[v]));
    reverse((res).begin(), (res).end());
    return res;
  }
} tree;
struct Edge {
  int u, v, w;
  void read() { scanf("%d%d%d", &u, &v, &w); }
};
struct Qry {
  int u, v, l, qid;
  void read(int i) {
    qid = i;
    scanf("%d%d%d", &u, &v, &l);
  }
};
int n, q;
int f[MAXN];
int ans[MAXN];
Edge e[MAXN];
Qry qrys[MAXN];
struct Dat {
  int p, s, cnt, sum;
  void print() { printf(" p %d s %d cnt %d sum %d\n", p, s, cnt, sum); }
};
Dat operator+(const Dat& lhs, const Dat& rhs) {
  Dat res;
  res.cnt = lhs.cnt + rhs.cnt;
  res.sum = lhs.sum + rhs.sum - f[lhs.s] - f[rhs.p] + f[lhs.s + rhs.p];
  res.p = lhs.p;
  if (lhs.p == lhs.cnt) res.p += rhs.p;
  res.s = rhs.s;
  if (rhs.s == rhs.cnt) res.s += lhs.s;
  return res;
}
Dat dat[MAXN * 3];
void init(int id, int l, int r) {
  if (l == r) {
    dat[id] = Dat{0, 0, 1, 0};
    return;
  }
  int mid = (l + r) / 2;
  init(id * 2, l, mid);
  init(id * 2 + 1, mid + 1, r);
  dat[id] = dat[id * 2] + dat[id * 2 + 1];
  return;
}
void upd(int id, int l, int r, int x) {
  if (x < l || r < x) return;
  if (l == r) {
    dat[id] = Dat{1, 1, 1, f[1]};
    return;
  }
  int mid = (l + r) / 2;
  upd(id * 2, l, mid, x);
  upd(id * 2 + 1, mid + 1, r, x);
  dat[id] = dat[id * 2] + dat[id * 2 + 1];
  return;
}
Dat qry(int id, int l, int r, int a, int b) {
  if (b < l || r < a || a > b) return Dat{0, 0, 0, 0};
  if (a <= l && r <= b) return dat[id];
  int mid = (l + r) / 2;
  Dat r1 = qry(id * 2, l, mid, a, b);
  Dat r2 = qry(id * 2 + 1, mid + 1, r, a, b);
  return r1 + r2;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = (1); i <= (n - 1); i++) scanf("%d", f + i);
  for (int i = (1); i <= (n - 1); i++) e[i].read();
  for (int i = (1); i <= (q); i++) qrys[i].read(i);
  tree.init(n);
  for (int i = (1); i <= (n - 1); i++) tree.addEdge(e[i].u, e[i].v);
  tree.yutruli();
  sort(e + 1, e + 1 + n - 1, [&](Edge a, Edge b) { return a.w > b.w; });
  sort(qrys + 1, qrys + 1 + q, [&](Qry a, Qry b) { return a.l > b.l; });
  int j = 1;
  init(1, 1, n);
  for (int i = (1); i <= (q); i++) {
    while (j <= n - 1 && qrys[i].l <= e[j].w) {
      int u = e[j].u, v = e[j].v;
      upd(1, 1, n, max(tree.tid[u], tree.tid[v]));
      j++;
    }
    int u = qrys[i].u;
    int v = qrys[i].v;
    int anc = tree.lca(u, v);
    vector<tuple<int, int> > path1 = tree.getPath(anc, u);
    get<0>(path1[0])++;
    vector<tuple<int, int> > path2 = tree.getPath(anc, v);
    get<0>(path2[0])++;
    Dat r1{0, 0, 0, 0}, r2{0, 0, 0, 0};
    for (tuple<int, int>& p : path1) {
      int a, b;
      tie(a, b) = p;
      r1 = r1 + qry(1, 1, n, a, b);
    }
    swap(r1.p, r1.s);
    for (tuple<int, int>& p : path2) {
      int a, b;
      tie(a, b) = p;
      r2 = r2 + qry(1, 1, n, a, b);
    }
    Dat res = r1 + r2;
    ans[qrys[i].qid] = res.sum;
  }
  for (int i = (1); i <= (q); i++) printf("%d\n", ans[i]);
}

### 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 double EPS = -1e8;
const double Pi = acos(-1);
bool inline equ(double a, double b) { return fabs(a - b) < EPS; }
const int MAXN = 100010;
const int LOG = 19;
struct HLD {
  int n;
  vector<int> g[MAXN];
  int sz[MAXN], dep[MAXN];
  int ts, tid[MAXN], tdi[MAXN], tl[MAXN], tr[MAXN];
  int mom[MAXN][LOG], head[MAXN];
  void dfssz(int u, int p) {
    dep[u] = dep[p] + 1;
    mom[u][0] = p;
    sz[u] = 1;
    head[u] = u;
    for (int& v : g[u])
      if (v != p) {
        dep[v] = dep[u] + 1;
        dfssz(v, u);
        sz[u] += sz[v];
      }
  }
  void dfshl(int u) {
    ts++;
    tid[u] = tl[u] = tr[u] = ts;
    tdi[tid[u]] = u;
    sort((g[u]).begin(), (g[u]).end(),
         [&](int a, int b) { return sz[a] > sz[b]; });
    bool flag = 1;
    for (int& v : g[u])
      if (v != mom[u][0]) {
        if (flag) head[v] = head[u], flag = 0;
        dfshl(v);
        tr[u] = tr[v];
      }
  }
  inline int lca(int a, int b) {
    if (dep[a] > dep[b]) swap(a, b);
    int diff = dep[b] - dep[a];
    for (int k = (LOG - 1); k >= (0); k--)
      if (diff & (1 << k)) {
        b = mom[b][k];
      }
    if (a == b) return a;
    for (int k = (LOG - 1); k >= (0); k--)
      if (mom[a][k] != mom[b][k]) {
        a = mom[a][k];
        b = mom[b][k];
      }
    return mom[a][0];
  }
  void init(int _n) {
    n = _n;
    for (int i = (1); i <= (n); i++) g[i].clear();
  }
  void addEdge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
  }
  void yutruli() {
    dfssz(1, 0);
    ts = 0;
    dfshl(1);
    for (int k = (1); k <= (LOG - 1); k++)
      for (int i = (1); i <= (n); i++) mom[i][k] = mom[mom[i][k - 1]][k - 1];
  }
  vector<tuple<int, int> > getPath(int u, int v) {
    vector<tuple<int, int> > res;
    while (tid[u] < tid[head[v]]) {
      res.push_back(tuple<int, int>(tid[head[v]], tid[v]));
      v = mom[head[v]][0];
    }
    res.push_back(tuple<int, int>(tid[u], tid[v]));
    reverse((res).begin(), (res).end());
    return res;
  }
} tree;
struct Edge {
  int u, v, w;
  void read() { scanf("%d%d%d", &u, &v, &w); }
};
struct Qry {
  int u, v, l, qid;
  void read(int i) {
    qid = i;
    scanf("%d%d%d", &u, &v, &l);
  }
};
int n, q;
int f[MAXN];
int ans[MAXN];
Edge e[MAXN];
Qry qrys[MAXN];
struct Dat {
  int p, s, cnt, sum;
  void print() { printf(" p %d s %d cnt %d sum %d\n", p, s, cnt, sum); }
};
Dat operator+(const Dat& lhs, const Dat& rhs) {
  Dat res;
  res.cnt = lhs.cnt + rhs.cnt;
  res.sum = lhs.sum + rhs.sum - f[lhs.s] - f[rhs.p] + f[lhs.s + rhs.p];
  res.p = lhs.p;
  if (lhs.p == lhs.cnt) res.p += rhs.p;
  res.s = rhs.s;
  if (rhs.s == rhs.cnt) res.s += lhs.s;
  return res;
}
Dat dat[MAXN * 3];
void init(int id, int l, int r) {
  if (l == r) {
    dat[id] = Dat{0, 0, 1, 0};
    return;
  }
  int mid = (l + r) / 2;
  init(id * 2, l, mid);
  init(id * 2 + 1, mid + 1, r);
  dat[id] = dat[id * 2] + dat[id * 2 + 1];
  return;
}
void upd(int id, int l, int r, int x) {
  if (x < l || r < x) return;
  if (l == r) {
    dat[id] = Dat{1, 1, 1, f[1]};
    return;
  }
  int mid = (l + r) / 2;
  upd(id * 2, l, mid, x);
  upd(id * 2 + 1, mid + 1, r, x);
  dat[id] = dat[id * 2] + dat[id * 2 + 1];
  return;
}
Dat qry(int id, int l, int r, int a, int b) {
  if (b < l || r < a || a > b) return Dat{0, 0, 0, 0};
  if (a <= l && r <= b) return dat[id];
  int mid = (l + r) / 2;
  Dat r1 = qry(id * 2, l, mid, a, b);
  Dat r2 = qry(id * 2 + 1, mid + 1, r, a, b);
  return r1 + r2;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = (1); i <= (n - 1); i++) scanf("%d", f + i);
  for (int i = (1); i <= (n - 1); i++) e[i].read();
  for (int i = (1); i <= (q); i++) qrys[i].read(i);
  tree.init(n);
  for (int i = (1); i <= (n - 1); i++) tree.addEdge(e[i].u, e[i].v);
  tree.yutruli();
  sort(e + 1, e + 1 + n - 1, [&](Edge a, Edge b) { return a.w > b.w; });
  sort(qrys + 1, qrys + 1 + q, [&](Qry a, Qry b) { return a.l > b.l; });
  int j = 1;
  init(1, 1, n);
  for (int i = (1); i <= (q); i++) {
    while (j <= n - 1 && qrys[i].l <= e[j].w) {
      int u = e[j].u, v = e[j].v;
      upd(1, 1, n, max(tree.tid[u], tree.tid[v]));
      j++;
    }
    int u = qrys[i].u;
    int v = qrys[i].v;
    int anc = tree.lca(u, v);
    vector<tuple<int, int> > path1 = tree.getPath(anc, u);
    get<0>(path1[0])++;
    vector<tuple<int, int> > path2 = tree.getPath(anc, v);
    get<0>(path2[0])++;
    Dat r1{0, 0, 0, 0}, r2{0, 0, 0, 0};
    for (tuple<int, int>& p : path1) {
      int a, b;
      tie(a, b) = p;
      r1 = r1 + qry(1, 1, n, a, b);
    }
    swap(r1.p, r1.s);
    for (tuple<int, int>& p : path2) {
      int a, b;
      tie(a, b) = p;
      r2 = r2 + qry(1, 1, n, a, b);
    }
    Dat res = r1 + r2;
    ans[qrys[i].qid] = res.sum;
  }
  for (int i = (1); i <= (q); i++) printf("%d\n", ans[i]);
}

```