#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e5 + 5, lg = 16;
struct updates {
  int l, x, y, id;
  bool operator<(const updates &other) const {
    if (l != other.l) return l > other.l;
    return id < other.id;
  }
};
vector<updates> upd;
vector<int> v[Nmax];
struct Node {
  int s, l, r;
  bool full;
  Node() { s = l = r = full = 0; }
  Node(int S, int L, int R, bool Full) {
    s = S;
    l = L;
    r = R;
    full = Full;
  }
};
int f[Nmax], x, y, w, i, answer[Nmax], n, q;
Node combina(Node a, Node b) {
  if (a.full && b.full) return Node(0, a.l + b.l, a.r + b.r, 1);
  if (a.full) return Node(b.s, a.l + b.l, b.r, 0);
  if (b.full) return Node(a.s, a.l, a.r + b.r, 0);
  return Node(a.s + b.s + f[a.r + b.l], a.l, b.r, 0);
}
class SegmentTree {
  Node *a;

 public:
  void build(int sz) { a = new Node[4 * sz + 5]; }
  void update(int node, int st, int dr, int pos) {
    if (st == dr) {
      a[node].s = 0;
      a[node].l = a[node].r = a[node].full = 1;
      return;
    }
    if (pos <= ((st + dr) / 2))
      update((node << 1), st, ((st + dr) / 2), pos);
    else
      update(((node << 1) + 1), ((st + dr) / 2) + 1, dr, pos);
    a[node] = combina(a[(node << 1)], a[((node << 1) + 1)]);
  }
  Node query(int node, int st, int dr, int Left, int Right) {
    if (Left <= st && dr <= Right) return a[node];
    if (Left <= ((st + dr) / 2) && ((st + dr) / 2) < Right)
      return combina(
          query((node << 1), st, ((st + dr) / 2), Left, Right),
          query(((node << 1) + 1), ((st + dr) / 2) + 1, dr, Left, Right));
    if (Left <= ((st + dr) / 2))
      return query((node << 1), st, ((st + dr) / 2), Left, Right);
    else
      return query(((node << 1) + 1), ((st + dr) / 2) + 1, dr, Left, Right);
  }
} aint[Nmax];
class HeavyPath {
  int level[Nmax], dad[Nmax], to[Nmax], pos[Nmax], w[Nmax], sz[Nmax],
      First[Nmax], t[Nmax][lg + 2], nrChains;
  void dfs(int node) {
    for (auto i = 1; i <= lg; ++i) t[node][i] = t[t[node][i - 1]][i - 1];
    w[node] = 1;
    for (auto it : v[node])
      if (!level[it]) {
        level[it] = level[node] + 1;
        dad[it] = t[it][0] = node;
        dfs(it);
        w[node] += w[it];
      }
  }
  void chains(int node) {
    to[node] = nrChains;
    pos[node] = ++sz[nrChains];
    if (v[node].size() == 1 && node != 1) return;
    int xson = 0;
    for (auto it : v[node])
      if (it != dad[node] && w[xson] < w[it]) xson = it;
    chains(xson);
    for (auto it : v[node])
      if (it != dad[node] && it != xson) {
        First[++nrChains] = it;
        chains(it);
      }
  }
  Node query(int x, int y) {
    if (to[x] == to[y])
      return aint[to[x]].query(1, 1, sz[to[x]], pos[x], pos[y]);
    return combina(query(x, dad[First[to[y]]]),
                   aint[to[y]].query(1, 1, sz[to[y]], 1, pos[y]));
  }

 public:
  void prepare() {
    memset(level, 0, sizeof(level));
    level[1] = 1;
    dad[1] = 0;
    dfs(1);
    nrChains = 1;
    First[1] = 1;
    memset(sz, 0, sizeof(sz));
    chains(1);
    int i;
    for (i = 1; i <= nrChains; ++i) aint[i].build(sz[i]);
  }
  int get_answer(int x, int y) {
    int X = x, Y = y;
    if (level[x] < level[y]) swap(x, y), swap(X, Y);
    int up = level[x] - level[y] - 1, i;
    if (up != -1) {
      for (i = 0; i <= lg; ++i)
        if (up & (1 << i)) x = t[x][i];
      if (dad[x] == y) {
        auto ans = query(x, X);
        if (ans.full) return f[ans.l];
        return ans.s + f[ans.l] + f[ans.r];
      }
      x = dad[x];
    }
    for (i = lg; i >= 0; --i)
      if (t[x][i] != t[y][i]) x = t[x][i], y = t[y][i];
    auto ans1 = query(x, X), ans2 = query(y, Y);
    swap(ans2.l, ans2.r);
    ans1 = combina(ans2, ans1);
    if (ans1.full) return f[ans1.l];
    return ans1.s + f[ans1.l] + f[ans1.r];
  }
  void add_edge(int x, int y) {
    if (y == dad[x]) swap(x, y);
    aint[to[y]].update(1, 1, sz[to[y]], pos[y]);
  }
} hp;
int main() {
  cin.sync_with_stdio(false);
  cin >> n >> q;
  for (i = 1; i < n; ++i) cin >> f[i];
  for (i = 1; i < n; ++i) {
    cin >> x >> y >> w;
    v[x].push_back(y);
    v[y].push_back(x);
    upd.push_back({w, x, y, 0});
  }
  for (i = 1; i <= q; ++i) {
    cin >> x >> y >> w;
    upd.push_back({w, x, y, i});
  }
  sort(upd.begin(), upd.end());
  hp.prepare();
  for (auto it : upd) {
    if (!it.id)
      hp.add_edge(it.x, it.y);
    else
      answer[it.id] = hp.get_answer(it.x, it.y);
  }
  for (i = 1; i <= q; ++i) cout << answer[i] << '\n';
  return 0;
}

### Prompt

Your task is to create 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 Nmax = 1e5 + 5, lg = 16;
struct updates {
  int l, x, y, id;
  bool operator<(const updates &other) const {
    if (l != other.l) return l > other.l;
    return id < other.id;
  }
};
vector<updates> upd;
vector<int> v[Nmax];
struct Node {
  int s, l, r;
  bool full;
  Node() { s = l = r = full = 0; }
  Node(int S, int L, int R, bool Full) {
    s = S;
    l = L;
    r = R;
    full = Full;
  }
};
int f[Nmax], x, y, w, i, answer[Nmax], n, q;
Node combina(Node a, Node b) {
  if (a.full && b.full) return Node(0, a.l + b.l, a.r + b.r, 1);
  if (a.full) return Node(b.s, a.l + b.l, b.r, 0);
  if (b.full) return Node(a.s, a.l, a.r + b.r, 0);
  return Node(a.s + b.s + f[a.r + b.l], a.l, b.r, 0);
}
class SegmentTree {
  Node *a;

 public:
  void build(int sz) { a = new Node[4 * sz + 5]; }
  void update(int node, int st, int dr, int pos) {
    if (st == dr) {
      a[node].s = 0;
      a[node].l = a[node].r = a[node].full = 1;
      return;
    }
    if (pos <= ((st + dr) / 2))
      update((node << 1), st, ((st + dr) / 2), pos);
    else
      update(((node << 1) + 1), ((st + dr) / 2) + 1, dr, pos);
    a[node] = combina(a[(node << 1)], a[((node << 1) + 1)]);
  }
  Node query(int node, int st, int dr, int Left, int Right) {
    if (Left <= st && dr <= Right) return a[node];
    if (Left <= ((st + dr) / 2) && ((st + dr) / 2) < Right)
      return combina(
          query((node << 1), st, ((st + dr) / 2), Left, Right),
          query(((node << 1) + 1), ((st + dr) / 2) + 1, dr, Left, Right));
    if (Left <= ((st + dr) / 2))
      return query((node << 1), st, ((st + dr) / 2), Left, Right);
    else
      return query(((node << 1) + 1), ((st + dr) / 2) + 1, dr, Left, Right);
  }
} aint[Nmax];
class HeavyPath {
  int level[Nmax], dad[Nmax], to[Nmax], pos[Nmax], w[Nmax], sz[Nmax],
      First[Nmax], t[Nmax][lg + 2], nrChains;
  void dfs(int node) {
    for (auto i = 1; i <= lg; ++i) t[node][i] = t[t[node][i - 1]][i - 1];
    w[node] = 1;
    for (auto it : v[node])
      if (!level[it]) {
        level[it] = level[node] + 1;
        dad[it] = t[it][0] = node;
        dfs(it);
        w[node] += w[it];
      }
  }
  void chains(int node) {
    to[node] = nrChains;
    pos[node] = ++sz[nrChains];
    if (v[node].size() == 1 && node != 1) return;
    int xson = 0;
    for (auto it : v[node])
      if (it != dad[node] && w[xson] < w[it]) xson = it;
    chains(xson);
    for (auto it : v[node])
      if (it != dad[node] && it != xson) {
        First[++nrChains] = it;
        chains(it);
      }
  }
  Node query(int x, int y) {
    if (to[x] == to[y])
      return aint[to[x]].query(1, 1, sz[to[x]], pos[x], pos[y]);
    return combina(query(x, dad[First[to[y]]]),
                   aint[to[y]].query(1, 1, sz[to[y]], 1, pos[y]));
  }

 public:
  void prepare() {
    memset(level, 0, sizeof(level));
    level[1] = 1;
    dad[1] = 0;
    dfs(1);
    nrChains = 1;
    First[1] = 1;
    memset(sz, 0, sizeof(sz));
    chains(1);
    int i;
    for (i = 1; i <= nrChains; ++i) aint[i].build(sz[i]);
  }
  int get_answer(int x, int y) {
    int X = x, Y = y;
    if (level[x] < level[y]) swap(x, y), swap(X, Y);
    int up = level[x] - level[y] - 1, i;
    if (up != -1) {
      for (i = 0; i <= lg; ++i)
        if (up & (1 << i)) x = t[x][i];
      if (dad[x] == y) {
        auto ans = query(x, X);
        if (ans.full) return f[ans.l];
        return ans.s + f[ans.l] + f[ans.r];
      }
      x = dad[x];
    }
    for (i = lg; i >= 0; --i)
      if (t[x][i] != t[y][i]) x = t[x][i], y = t[y][i];
    auto ans1 = query(x, X), ans2 = query(y, Y);
    swap(ans2.l, ans2.r);
    ans1 = combina(ans2, ans1);
    if (ans1.full) return f[ans1.l];
    return ans1.s + f[ans1.l] + f[ans1.r];
  }
  void add_edge(int x, int y) {
    if (y == dad[x]) swap(x, y);
    aint[to[y]].update(1, 1, sz[to[y]], pos[y]);
  }
} hp;
int main() {
  cin.sync_with_stdio(false);
  cin >> n >> q;
  for (i = 1; i < n; ++i) cin >> f[i];
  for (i = 1; i < n; ++i) {
    cin >> x >> y >> w;
    v[x].push_back(y);
    v[y].push_back(x);
    upd.push_back({w, x, y, 0});
  }
  for (i = 1; i <= q; ++i) {
    cin >> x >> y >> w;
    upd.push_back({w, x, y, i});
  }
  sort(upd.begin(), upd.end());
  hp.prepare();
  for (auto it : upd) {
    if (!it.id)
      hp.add_edge(it.x, it.y);
    else
      answer[it.id] = hp.get_answer(it.x, it.y);
  }
  for (i = 1; i <= q; ++i) cout << answer[i] << '\n';
  return 0;
}

```