#include <bits/stdc++.h>
using namespace std;
bool debug = 1;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
long long ln, lk, lm;
vector<pair<int, int>> mp[100105], egs;
int F[100105], eg[100105], p[100105][20], d[100105];
int st[100105], ed[100105], cnt = 1, sz[100105];
int chain = 1, be[100105], head[100105], top[100105];
bool vc[100105];
void calSize(int x, int pa) {
  sz[x] = 1;
  for (auto c : mp[x])
    if (c.first != pa) {
      calSize(c.first, x);
      sz[x] += sz[c.first];
    }
}
void dfs(int x, int pa, int w) {
  st[x] = cnt;
  p[x][0] = pa;
  d[x] = d[pa] + 1;
  eg[cnt] = w;
  if (x != 1) {
    egs.push_back({w, cnt});
  }
  cnt++;
  be[x] = chain;
  if (!vc[chain]) {
    vc[chain] = 1;
    head[chain] = x;
    top[chain] = pa;
  }
  int mx = -1;
  for (auto c : mp[x])
    if (c.first != pa) mx = max(mx, sz[c.first]);
  for (auto c : mp[x])
    if (c.first != pa && sz[c.first] == mx) dfs(c.first, x, c.second);
  for (auto c : mp[x])
    if (c.first != pa && sz[c.first] != mx) dfs(c.first, x, c.second);
  ed[x] = cnt;
  if (mx == -1) chain++;
}
void initLca() {
  for (int j = 1; j < 20; j++)
    for (int i = 1; i <= n; i++) p[i][j] = p[p[i][j - 1]][j - 1];
}
int lca(int a, int b) {
  if (d[a] > d[b]) swap(a, b);
  int f = d[b] - d[a];
  for (int i = 0; (1 << i) <= f; i++)
    if ((1 << i) & f) b = p[b][i];
  if (a != b) {
    for (int i = 19; i >= 0; i--)
      if (p[a][i] != p[b][i]) {
        a = p[a][i];
        b = p[b][i];
      }
    a = p[a][0];
  }
  return a;
}
struct node {
  int l = 0, r = 0, ans = 0, spec = 0;
  bool all = 0;
  void st(int a, int b, int c, bool f) {
    l = a;
    r = b;
    ans = c;
    all = f;
  }
  void setSpec() {
    spec = 1;
    l = 0;
    r = 0;
    ans = 0;
    all = 0;
  }
  void cp(node &o) {
    l = o.l;
    r = o.r;
    ans = o.ans;
    all = o.all;
  }
  void merge(node &a, node &b) {
    if (a.spec && b.spec) {
      setSpec();
      return;
    }
    if (a.spec) {
      cp(b);
      return;
    }
    if (b.spec) {
      cp(a);
      return;
    }
    if (a.all && b.all) {
      st(a.l + b.l, a.r + b.r, 0, 1);
      assert(l == r);
    } else if (a.all) {
      st(a.r + b.l, b.r, b.ans, 0);
    } else if (b.all) {
      st(a.l, a.r + b.l, a.ans, 0);
    } else {
      int x = a.ans + b.ans + F[a.r + b.l];
      st(a.l, b.r, x, 0);
    }
  }
};
node tree[100105 * 4], SPEC;
void upt(int rt, int l, int r, int L) {
  if (l + 1 == r) {
    tree[rt].st(1, 1, 0, 1);
    return;
  }
  int mid = (l + r) / 2;
  if (L <= mid)
    upt((rt << 1), l, mid, L);
  else
    upt((rt << 1 | 1), mid, r, L);
  tree[rt].merge(tree[(rt << 1)], tree[(rt << 1 | 1)]);
}
node qy(int rt, int l, int r, int L, int R) {
  if (r <= L || R <= l) return SPEC;
  if (L <= l && r <= R) return tree[rt];
  int mid = (l + r) / 2;
  node a = qy((rt << 1), l, mid, L, R);
  node b = qy((rt << 1 | 1), mid, r, L, R);
  node c = node();
  c.merge(a, b);
  return c;
}
node cal(int u, int fa) {
  if (u == fa) return SPEC;
  if (be[u] == be[fa]) {
    return qy(1, 1, cnt - 1, st[fa], st[u]);
  }
  node b = qy(1, 1, cnt - 1, st[head[be[u]]] - 1, st[u]);
  node a = cal(top[be[u]], fa);
  node c = node();
  c.merge(a, b);
  return c;
}
struct QQ {
  int u, v, l, id;
  void rd() { scanf("%d%d%d", &u, &v, &l); }
  bool operator<(const QQ &o) const { return l > o.l; }
} qq[100105];
int Ans[100105];
int main() {
  scanf("%d%d", &n, &m);
  debug = n == 100000;
  for (int(i) = 1; (i) <= (int)(n - 1); (i)++) scanf("%d", F + i);
  for (int u, v, w, i = 0; i < n - 1; i++) {
    scanf("%d%d%d", &u, &v, &w);
    mp[u].push_back({v, w});
    mp[v].push_back({u, w});
  }
  calSize(1, 0);
  dfs(1, 0, 0);
  initLca();
  sort(egs.begin(), egs.end());
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    qq[i].rd();
    qq[i].id = i;
  }
  sort(qq + 1, qq + 1 + m);
  SPEC = node();
  SPEC.setSpec();
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    while (!egs.empty() && egs.back().first >= qq[i].l) {
      upt(1, 1, cnt - 1, egs.back().second);
      egs.pop_back();
    }
    int u = qq[i].u, v = qq[i].v;
    int fa = lca(u, v);
    node a = cal(u, fa), b = cal(v, fa);
    node c = node();
    swap(a.l, a.r);
    c.merge(a, b);
    int ans = c.ans;
    if (c.all)
      ans += F[c.l];
    else
      ans += F[c.l] + F[c.r];
    Ans[qq[i].id] = ans;
    if (qq[i].id == 1 && debug) {
    }
  }
  for (int(i) = 1; (i) <= (int)(m); (i)++) printf("%d\n", Ans[i]);
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
bool debug = 1;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
long long ln, lk, lm;
vector<pair<int, int>> mp[100105], egs;
int F[100105], eg[100105], p[100105][20], d[100105];
int st[100105], ed[100105], cnt = 1, sz[100105];
int chain = 1, be[100105], head[100105], top[100105];
bool vc[100105];
void calSize(int x, int pa) {
  sz[x] = 1;
  for (auto c : mp[x])
    if (c.first != pa) {
      calSize(c.first, x);
      sz[x] += sz[c.first];
    }
}
void dfs(int x, int pa, int w) {
  st[x] = cnt;
  p[x][0] = pa;
  d[x] = d[pa] + 1;
  eg[cnt] = w;
  if (x != 1) {
    egs.push_back({w, cnt});
  }
  cnt++;
  be[x] = chain;
  if (!vc[chain]) {
    vc[chain] = 1;
    head[chain] = x;
    top[chain] = pa;
  }
  int mx = -1;
  for (auto c : mp[x])
    if (c.first != pa) mx = max(mx, sz[c.first]);
  for (auto c : mp[x])
    if (c.first != pa && sz[c.first] == mx) dfs(c.first, x, c.second);
  for (auto c : mp[x])
    if (c.first != pa && sz[c.first] != mx) dfs(c.first, x, c.second);
  ed[x] = cnt;
  if (mx == -1) chain++;
}
void initLca() {
  for (int j = 1; j < 20; j++)
    for (int i = 1; i <= n; i++) p[i][j] = p[p[i][j - 1]][j - 1];
}
int lca(int a, int b) {
  if (d[a] > d[b]) swap(a, b);
  int f = d[b] - d[a];
  for (int i = 0; (1 << i) <= f; i++)
    if ((1 << i) & f) b = p[b][i];
  if (a != b) {
    for (int i = 19; i >= 0; i--)
      if (p[a][i] != p[b][i]) {
        a = p[a][i];
        b = p[b][i];
      }
    a = p[a][0];
  }
  return a;
}
struct node {
  int l = 0, r = 0, ans = 0, spec = 0;
  bool all = 0;
  void st(int a, int b, int c, bool f) {
    l = a;
    r = b;
    ans = c;
    all = f;
  }
  void setSpec() {
    spec = 1;
    l = 0;
    r = 0;
    ans = 0;
    all = 0;
  }
  void cp(node &o) {
    l = o.l;
    r = o.r;
    ans = o.ans;
    all = o.all;
  }
  void merge(node &a, node &b) {
    if (a.spec && b.spec) {
      setSpec();
      return;
    }
    if (a.spec) {
      cp(b);
      return;
    }
    if (b.spec) {
      cp(a);
      return;
    }
    if (a.all && b.all) {
      st(a.l + b.l, a.r + b.r, 0, 1);
      assert(l == r);
    } else if (a.all) {
      st(a.r + b.l, b.r, b.ans, 0);
    } else if (b.all) {
      st(a.l, a.r + b.l, a.ans, 0);
    } else {
      int x = a.ans + b.ans + F[a.r + b.l];
      st(a.l, b.r, x, 0);
    }
  }
};
node tree[100105 * 4], SPEC;
void upt(int rt, int l, int r, int L) {
  if (l + 1 == r) {
    tree[rt].st(1, 1, 0, 1);
    return;
  }
  int mid = (l + r) / 2;
  if (L <= mid)
    upt((rt << 1), l, mid, L);
  else
    upt((rt << 1 | 1), mid, r, L);
  tree[rt].merge(tree[(rt << 1)], tree[(rt << 1 | 1)]);
}
node qy(int rt, int l, int r, int L, int R) {
  if (r <= L || R <= l) return SPEC;
  if (L <= l && r <= R) return tree[rt];
  int mid = (l + r) / 2;
  node a = qy((rt << 1), l, mid, L, R);
  node b = qy((rt << 1 | 1), mid, r, L, R);
  node c = node();
  c.merge(a, b);
  return c;
}
node cal(int u, int fa) {
  if (u == fa) return SPEC;
  if (be[u] == be[fa]) {
    return qy(1, 1, cnt - 1, st[fa], st[u]);
  }
  node b = qy(1, 1, cnt - 1, st[head[be[u]]] - 1, st[u]);
  node a = cal(top[be[u]], fa);
  node c = node();
  c.merge(a, b);
  return c;
}
struct QQ {
  int u, v, l, id;
  void rd() { scanf("%d%d%d", &u, &v, &l); }
  bool operator<(const QQ &o) const { return l > o.l; }
} qq[100105];
int Ans[100105];
int main() {
  scanf("%d%d", &n, &m);
  debug = n == 100000;
  for (int(i) = 1; (i) <= (int)(n - 1); (i)++) scanf("%d", F + i);
  for (int u, v, w, i = 0; i < n - 1; i++) {
    scanf("%d%d%d", &u, &v, &w);
    mp[u].push_back({v, w});
    mp[v].push_back({u, w});
  }
  calSize(1, 0);
  dfs(1, 0, 0);
  initLca();
  sort(egs.begin(), egs.end());
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    qq[i].rd();
    qq[i].id = i;
  }
  sort(qq + 1, qq + 1 + m);
  SPEC = node();
  SPEC.setSpec();
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    while (!egs.empty() && egs.back().first >= qq[i].l) {
      upt(1, 1, cnt - 1, egs.back().second);
      egs.pop_back();
    }
    int u = qq[i].u, v = qq[i].v;
    int fa = lca(u, v);
    node a = cal(u, fa), b = cal(v, fa);
    node c = node();
    swap(a.l, a.r);
    c.merge(a, b);
    int ans = c.ans;
    if (c.all)
      ans += F[c.l];
    else
      ans += F[c.l] + F[c.r];
    Ans[qq[i].id] = ans;
    if (qq[i].id == 1 && debug) {
    }
  }
  for (int(i) = 1; (i) <= (int)(m); (i)++) printf("%d\n", Ans[i]);
  return 0;
}

```