#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int LOG = 19;
int n, m, f[MAXN], ans[MAXN], depth[MAXN], par[LOG][MAXN], subsz[MAXN];
int s_t[MAXN], f_t[MAXN], tm, sz;
int chain_id[MAXN], chain_sz[MAXN], pos[MAXN], head[MAXN], cur;
vector<pair<int, int>> adj[MAXN];
pair<pair<int, int>, pair<int, int>> que[MAXN];
pair<int, int> sec[MAXN];
pair<pair<int, int>, pair<int, int>> NL, weed[4 * MAXN];
bool cmp(pair<pair<int, int>, pair<int, int>> a,
         pair<pair<int, int>, pair<int, int>> b) {
  return a.second.first > b.second.first;
}
void dfs(int v = 0, int p = -1, int w = 0) {
  depth[v] = (~p ? depth[p] + 1 : 0);
  par[0][v] = p;
  subsz[v] = 1;
  for (auto e : adj[v])
    if (e.first ^ p) dfs(e.first, v, e.second), subsz[v] += subsz[e.first];
  if (~p) sec[sz++] = {w, v};
}
void preLca() {
  for (int w = 1; w < LOG; w++)
    for (int i = 0; i < n; i++)
      par[w][i] = (~par[w - 1][i] ? par[w - 1][par[w - 1][i]] : -1);
}
int lca(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  for (int w = LOG - 1; ~w; w--)
    if (depth[u] - (1 << w) >= depth[v]) u = par[w][u];
  if (u == v) return u;
  for (int w = LOG - 1; w >= 0; w--)
    if (par[w][u] ^ par[w][v]) u = par[w][u], v = par[w][v];
  return par[0][v];
}
void hld(int v = 0) {
  if (head[cur] == -1) head[cur] = v;
  pos[v] = chain_sz[cur]++;
  chain_id[v] = cur;
  s_t[v] = tm++;
  pair<int, int> mx(-1, -1);
  for (auto e : adj[v])
    if (e.first ^ par[0][v]) mx = max(mx, make_pair(subsz[e.first], e.first));
  if (~mx.first) hld(mx.second);
  for (auto e : adj[v])
    if (e.first ^ par[0][v] && e.first ^ mx.second) cur++, hld(e.first);
  f_t[v] = tm;
}
pair<pair<int, int>, pair<int, int>> merge(
    pair<pair<int, int>, pair<int, int>> a,
    pair<pair<int, int>, pair<int, int>> b) {
  pair<pair<int, int>, pair<int, int>> ret;
  ret.second.first = a.second.first + b.second.first;
  ret.first.first =
      a.first.first + (a.first.first == a.second.first ? b.first.first : 0);
  ret.first.second =
      b.first.second + (b.first.second == b.second.first ? a.first.second : 0);
  ret.second.second =
      a.second.second + b.second.second +
      ((a.first.second != a.second.first && b.first.first != b.second.first)
           ? f[a.first.second + b.first.first]
           : 0);
  return ret;
}
void plant(int v = 1, int b = 0, int e = n) {
  weed[v].second.first = e - b;
  if (e - b == 1) return;
  int mid = (b + e) / 2;
  plant(v << 1, b, mid);
  plant(v << 1 ^ 1, mid, e);
}
void water(int v, int b, int e, int x) {
  if (e - b == 1) {
    weed[v].first.first = weed[v].first.second = 1;
    return;
  }
  int mid = (b + e) / 2;
  if (x < mid)
    water(v << 1, b, mid, x);
  else
    water(v << 1 ^ 1, mid, e, x);
  weed[v] = merge(weed[v << 1], weed[v << 1 ^ 1]);
}
pair<pair<int, int>, pair<int, int>> smoke(int v, int b, int e, int l, int r) {
  if (l <= b && e <= r) return weed[v];
  if (r <= b || e <= l) return NL;
  int mid = (b + e) / 2;
  return merge(smoke(v << 1, b, mid, l, r), smoke(v << 1 ^ 1, mid, e, l, r));
}
pair<pair<int, int>, pair<int, int>> cal(int u, int p) {
  pair<pair<int, int>, pair<int, int>> ret = NL;
  while (u ^ p) {
    int dif = (depth[u] - depth[p]);
    if (pos[u] < dif)
      ret = merge(smoke(1, 0, n, s_t[u] - pos[u], s_t[u] + 1), ret),
      u = par[0][head[chain_id[u]]];
    else
      ret = merge(smoke(1, 0, n, s_t[u] + 1 - dif, s_t[u] + 1), ret), u = p;
  }
  return ret;
}
void solve(pair<pair<int, int>, pair<int, int>> x) {
  int u = x.first.first, v = x.first.second;
  int p = lca(u, v);
  pair<pair<int, int>, pair<int, int>> y = cal(u, p);
  pair<pair<int, int>, pair<int, int>> z = cal(v, p);
  swap(z.first.first, z.first.second);
  y = merge(z, y);
  ans[x.second.second] =
      y.second.second + f[y.first.first] +
      (y.first.first != y.second.first ? f[y.first.second] : 0);
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i < n; i++) scanf("%d", &f[i]);
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c), a--, b--;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }
  memset(head, -1, sizeof(head));
  dfs();
  preLca();
  hld();
  sort(sec, sec + sz, greater<pair<int, int>>());
  for (int i = 0; i < m; i++)
    scanf("%d %d %d", &que[i].first.first, &que[i].first.second,
          &que[i].second.first),
        que[i].second.second = i, que[i].first.first--, que[i].first.second--;
  sort(que, que + m, cmp);
  plant();
  int b = 0;
  for (int i = 0; i < sz; i++) {
    while (b < m && que[b].second.first > sec[i].first) solve(que[b++]);
    water(1, 0, n, s_t[sec[i].second]);
  }
  while (b < m) solve(que[b++]);
  for (int i = 0; i < 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;
const int MAXN = 1e5 + 10;
const int LOG = 19;
int n, m, f[MAXN], ans[MAXN], depth[MAXN], par[LOG][MAXN], subsz[MAXN];
int s_t[MAXN], f_t[MAXN], tm, sz;
int chain_id[MAXN], chain_sz[MAXN], pos[MAXN], head[MAXN], cur;
vector<pair<int, int>> adj[MAXN];
pair<pair<int, int>, pair<int, int>> que[MAXN];
pair<int, int> sec[MAXN];
pair<pair<int, int>, pair<int, int>> NL, weed[4 * MAXN];
bool cmp(pair<pair<int, int>, pair<int, int>> a,
         pair<pair<int, int>, pair<int, int>> b) {
  return a.second.first > b.second.first;
}
void dfs(int v = 0, int p = -1, int w = 0) {
  depth[v] = (~p ? depth[p] + 1 : 0);
  par[0][v] = p;
  subsz[v] = 1;
  for (auto e : adj[v])
    if (e.first ^ p) dfs(e.first, v, e.second), subsz[v] += subsz[e.first];
  if (~p) sec[sz++] = {w, v};
}
void preLca() {
  for (int w = 1; w < LOG; w++)
    for (int i = 0; i < n; i++)
      par[w][i] = (~par[w - 1][i] ? par[w - 1][par[w - 1][i]] : -1);
}
int lca(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  for (int w = LOG - 1; ~w; w--)
    if (depth[u] - (1 << w) >= depth[v]) u = par[w][u];
  if (u == v) return u;
  for (int w = LOG - 1; w >= 0; w--)
    if (par[w][u] ^ par[w][v]) u = par[w][u], v = par[w][v];
  return par[0][v];
}
void hld(int v = 0) {
  if (head[cur] == -1) head[cur] = v;
  pos[v] = chain_sz[cur]++;
  chain_id[v] = cur;
  s_t[v] = tm++;
  pair<int, int> mx(-1, -1);
  for (auto e : adj[v])
    if (e.first ^ par[0][v]) mx = max(mx, make_pair(subsz[e.first], e.first));
  if (~mx.first) hld(mx.second);
  for (auto e : adj[v])
    if (e.first ^ par[0][v] && e.first ^ mx.second) cur++, hld(e.first);
  f_t[v] = tm;
}
pair<pair<int, int>, pair<int, int>> merge(
    pair<pair<int, int>, pair<int, int>> a,
    pair<pair<int, int>, pair<int, int>> b) {
  pair<pair<int, int>, pair<int, int>> ret;
  ret.second.first = a.second.first + b.second.first;
  ret.first.first =
      a.first.first + (a.first.first == a.second.first ? b.first.first : 0);
  ret.first.second =
      b.first.second + (b.first.second == b.second.first ? a.first.second : 0);
  ret.second.second =
      a.second.second + b.second.second +
      ((a.first.second != a.second.first && b.first.first != b.second.first)
           ? f[a.first.second + b.first.first]
           : 0);
  return ret;
}
void plant(int v = 1, int b = 0, int e = n) {
  weed[v].second.first = e - b;
  if (e - b == 1) return;
  int mid = (b + e) / 2;
  plant(v << 1, b, mid);
  plant(v << 1 ^ 1, mid, e);
}
void water(int v, int b, int e, int x) {
  if (e - b == 1) {
    weed[v].first.first = weed[v].first.second = 1;
    return;
  }
  int mid = (b + e) / 2;
  if (x < mid)
    water(v << 1, b, mid, x);
  else
    water(v << 1 ^ 1, mid, e, x);
  weed[v] = merge(weed[v << 1], weed[v << 1 ^ 1]);
}
pair<pair<int, int>, pair<int, int>> smoke(int v, int b, int e, int l, int r) {
  if (l <= b && e <= r) return weed[v];
  if (r <= b || e <= l) return NL;
  int mid = (b + e) / 2;
  return merge(smoke(v << 1, b, mid, l, r), smoke(v << 1 ^ 1, mid, e, l, r));
}
pair<pair<int, int>, pair<int, int>> cal(int u, int p) {
  pair<pair<int, int>, pair<int, int>> ret = NL;
  while (u ^ p) {
    int dif = (depth[u] - depth[p]);
    if (pos[u] < dif)
      ret = merge(smoke(1, 0, n, s_t[u] - pos[u], s_t[u] + 1), ret),
      u = par[0][head[chain_id[u]]];
    else
      ret = merge(smoke(1, 0, n, s_t[u] + 1 - dif, s_t[u] + 1), ret), u = p;
  }
  return ret;
}
void solve(pair<pair<int, int>, pair<int, int>> x) {
  int u = x.first.first, v = x.first.second;
  int p = lca(u, v);
  pair<pair<int, int>, pair<int, int>> y = cal(u, p);
  pair<pair<int, int>, pair<int, int>> z = cal(v, p);
  swap(z.first.first, z.first.second);
  y = merge(z, y);
  ans[x.second.second] =
      y.second.second + f[y.first.first] +
      (y.first.first != y.second.first ? f[y.first.second] : 0);
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i < n; i++) scanf("%d", &f[i]);
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c), a--, b--;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }
  memset(head, -1, sizeof(head));
  dfs();
  preLca();
  hld();
  sort(sec, sec + sz, greater<pair<int, int>>());
  for (int i = 0; i < m; i++)
    scanf("%d %d %d", &que[i].first.first, &que[i].first.second,
          &que[i].second.first),
        que[i].second.second = i, que[i].first.first--, que[i].first.second--;
  sort(que, que + m, cmp);
  plant();
  int b = 0;
  for (int i = 0; i < sz; i++) {
    while (b < m && que[b].second.first > sec[i].first) solve(que[b++]);
    water(1, 0, n, s_t[sec[i].second]);
  }
  while (b < m) solve(que[b++]);
  for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
  return 0;
}

```