#include <bits/stdc++.h>
using namespace std;
int F[100001];
struct Data {
  int sz = 0, pref = 0, suf = 0, sum = 0;
};
inline Data merge(const Data &L, const Data &R) {
  Data ret;
  ret.sz = L.sz + R.sz;
  if (R.suf == R.sz) {
    ret.suf = L.suf + R.suf;
  } else {
    ret.suf = R.suf;
  }
  if (L.pref == L.sz) {
    ret.pref = L.pref + R.pref;
  } else {
    ret.pref = L.pref;
  }
  ret.sum = L.sum + R.sum;
  if (L.suf != L.sz && R.pref != R.sz) {
    ret.sum += F[L.suf + R.pref];
  }
  return ret;
}
struct Segtree {
  int N;
  vector<Data> A;
  inline void addNode() { N++; }
  void bld(int idx, int L, int R) {
    A[idx].sz = max(0, R - L + 1);
    if (L < R) {
      int M = L + R >> 1;
      bld(2 * idx, L, M);
      bld(2 * idx + 1, M + 1, R);
    }
  }
  inline void init() {
    A.assign(4 * N, Data());
    bld(1, 0, N - 1);
  }
  void upd(int idx, int L, int R, int x) {
    if (L == R) {
      A[idx].pref = A[idx].suf = 1;
    } else {
      int M = L + R >> 1;
      if (x <= M)
        upd(2 * idx, L, M, x);
      else
        upd(2 * idx + 1, M + 1, R, x);
      A[idx] = merge(A[2 * idx], A[2 * idx + 1]);
    }
  }
  Data qry(int idx, int L, int R, int l, int r) {
    l = max(L, l);
    r = min(R, r);
    if (l <= r) {
      if (L == l && R == r) {
        return A[idx];
      } else {
        int M = L + R >> 1;
        return merge(qry(2 * idx, L, M, l, r),
                     qry(2 * idx + 1, M + 1, R, l, r));
      }
    }
    return Data();
  }
  inline void update(int x) { upd(1, 0, N - 1, x); }
  inline Data query(int l, int r) { return qry(1, 0, N - 1, l, r); }
};
int N, Q;
vector<pair<int, int> > adj[100001];
pair<int, int> edges[100001];
int H[100001], sz[100001];
vector<Segtree> chain;
int par[100001];
pair<int, int> id[100001], edgeId[100001];
pair<pair<int, int>, pair<int, int> > qry[100001];
int ans[100001];
void computeSZ(int u, int p) {
  sz[u] = 1;
  for (const auto &v : adj[u]) {
    if (v.first == p) continue;
    computeSZ(v.first, u);
    sz[u] += sz[v.first];
  }
}
void buildHLD(int u, int p) {
  pair<int, int> hvy = {-1, 0};
  id[u].second = chain[id[u].first].N;
  chain[id[u].first].addNode();
  for (const auto &v : adj[u]) {
    if (v.first == p) continue;
    if (hvy.first == -1 || sz[v.first] > sz[hvy.first]) hvy = v;
  }
  for (const auto &v : adj[u]) {
    if (v.first != p && v != hvy) {
      H[v.first] = H[u] + 1;
      id[v.first].first = chain.size();
      par[v.first] = u;
      chain.push_back(Segtree());
      buildHLD(v.first, u);
      edgeId[v.second] = id[v.first];
      chain[id[v.first].first].init();
    }
  }
  if (hvy.first != -1) {
    par[hvy.first] = par[u];
    H[hvy.first] = H[u];
    id[hvy.first].first = id[u].first;
    buildHLD(hvy.first, u);
    edgeId[hvy.second] = id[hvy.first];
  }
}
inline void addEdge(int id) {
  pair<int, int> p = edgeId[id];
  chain[p.first].update(p.second);
}
inline int solve(int u, int v) {
  Data L, R;
  while (id[u].first != id[v].first) {
    if (H[u] > H[v]) {
      L = merge(chain[id[u].first].query(0, id[u].second), L);
      u = par[u];
    } else {
      R = merge(chain[id[v].first].query(0, id[v].second), R);
      v = par[v];
    }
  }
  if (id[v].second < id[u].second) {
    L = merge(chain[id[u].first].query(id[v].second + 1, id[u].second), L);
  } else if (id[u].second < id[v].second) {
    R = merge(chain[id[v].first].query(id[u].second + 1, id[v].second), R);
  }
  swap(L.pref, L.suf);
  R = merge(L, R);
  return ((R.suf == R.sz) ? F[R.sz] : (F[R.pref] + F[R.suf])) + R.sum;
}
int32_t main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> Q;
  for (int i = 1; i < N; i++) cin >> F[i];
  for (int i = 1; i < N; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u - 1].push_back({v - 1, i});
    adj[v - 1].push_back({u - 1, i});
    edges[i] = {w, i};
  }
  for (int i = 0; i < Q; i++) {
    cin >> qry[i].second.first >> qry[i].second.second >> qry[i].first.first;
    qry[i].second.first--;
    qry[i].second.second--;
    qry[i].first.second = i;
  }
  sort(edges + 1, edges + N, greater<pair<int, int> >());
  sort(qry, qry + Q, greater<pair<pair<int, int>, pair<int, int> > >());
  computeSZ(0, -1);
  chain.push_back(Segtree());
  par[0] = -1;
  buildHLD(0, -1);
  chain[0].init();
  int j = 1;
  for (int i = 0; i < Q; i++) {
    for (; j < N && edges[j].first >= qry[i].first.first; j++)
      addEdge(edges[j].second);
    ans[qry[i].first.second] = solve(qry[i].second.first, qry[i].second.second);
  }
  for (int i = 0; i < Q; i++) cout << ans[i] << "\n";
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
int F[100001];
struct Data {
  int sz = 0, pref = 0, suf = 0, sum = 0;
};
inline Data merge(const Data &L, const Data &R) {
  Data ret;
  ret.sz = L.sz + R.sz;
  if (R.suf == R.sz) {
    ret.suf = L.suf + R.suf;
  } else {
    ret.suf = R.suf;
  }
  if (L.pref == L.sz) {
    ret.pref = L.pref + R.pref;
  } else {
    ret.pref = L.pref;
  }
  ret.sum = L.sum + R.sum;
  if (L.suf != L.sz && R.pref != R.sz) {
    ret.sum += F[L.suf + R.pref];
  }
  return ret;
}
struct Segtree {
  int N;
  vector<Data> A;
  inline void addNode() { N++; }
  void bld(int idx, int L, int R) {
    A[idx].sz = max(0, R - L + 1);
    if (L < R) {
      int M = L + R >> 1;
      bld(2 * idx, L, M);
      bld(2 * idx + 1, M + 1, R);
    }
  }
  inline void init() {
    A.assign(4 * N, Data());
    bld(1, 0, N - 1);
  }
  void upd(int idx, int L, int R, int x) {
    if (L == R) {
      A[idx].pref = A[idx].suf = 1;
    } else {
      int M = L + R >> 1;
      if (x <= M)
        upd(2 * idx, L, M, x);
      else
        upd(2 * idx + 1, M + 1, R, x);
      A[idx] = merge(A[2 * idx], A[2 * idx + 1]);
    }
  }
  Data qry(int idx, int L, int R, int l, int r) {
    l = max(L, l);
    r = min(R, r);
    if (l <= r) {
      if (L == l && R == r) {
        return A[idx];
      } else {
        int M = L + R >> 1;
        return merge(qry(2 * idx, L, M, l, r),
                     qry(2 * idx + 1, M + 1, R, l, r));
      }
    }
    return Data();
  }
  inline void update(int x) { upd(1, 0, N - 1, x); }
  inline Data query(int l, int r) { return qry(1, 0, N - 1, l, r); }
};
int N, Q;
vector<pair<int, int> > adj[100001];
pair<int, int> edges[100001];
int H[100001], sz[100001];
vector<Segtree> chain;
int par[100001];
pair<int, int> id[100001], edgeId[100001];
pair<pair<int, int>, pair<int, int> > qry[100001];
int ans[100001];
void computeSZ(int u, int p) {
  sz[u] = 1;
  for (const auto &v : adj[u]) {
    if (v.first == p) continue;
    computeSZ(v.first, u);
    sz[u] += sz[v.first];
  }
}
void buildHLD(int u, int p) {
  pair<int, int> hvy = {-1, 0};
  id[u].second = chain[id[u].first].N;
  chain[id[u].first].addNode();
  for (const auto &v : adj[u]) {
    if (v.first == p) continue;
    if (hvy.first == -1 || sz[v.first] > sz[hvy.first]) hvy = v;
  }
  for (const auto &v : adj[u]) {
    if (v.first != p && v != hvy) {
      H[v.first] = H[u] + 1;
      id[v.first].first = chain.size();
      par[v.first] = u;
      chain.push_back(Segtree());
      buildHLD(v.first, u);
      edgeId[v.second] = id[v.first];
      chain[id[v.first].first].init();
    }
  }
  if (hvy.first != -1) {
    par[hvy.first] = par[u];
    H[hvy.first] = H[u];
    id[hvy.first].first = id[u].first;
    buildHLD(hvy.first, u);
    edgeId[hvy.second] = id[hvy.first];
  }
}
inline void addEdge(int id) {
  pair<int, int> p = edgeId[id];
  chain[p.first].update(p.second);
}
inline int solve(int u, int v) {
  Data L, R;
  while (id[u].first != id[v].first) {
    if (H[u] > H[v]) {
      L = merge(chain[id[u].first].query(0, id[u].second), L);
      u = par[u];
    } else {
      R = merge(chain[id[v].first].query(0, id[v].second), R);
      v = par[v];
    }
  }
  if (id[v].second < id[u].second) {
    L = merge(chain[id[u].first].query(id[v].second + 1, id[u].second), L);
  } else if (id[u].second < id[v].second) {
    R = merge(chain[id[v].first].query(id[u].second + 1, id[v].second), R);
  }
  swap(L.pref, L.suf);
  R = merge(L, R);
  return ((R.suf == R.sz) ? F[R.sz] : (F[R.pref] + F[R.suf])) + R.sum;
}
int32_t main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> Q;
  for (int i = 1; i < N; i++) cin >> F[i];
  for (int i = 1; i < N; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u - 1].push_back({v - 1, i});
    adj[v - 1].push_back({u - 1, i});
    edges[i] = {w, i};
  }
  for (int i = 0; i < Q; i++) {
    cin >> qry[i].second.first >> qry[i].second.second >> qry[i].first.first;
    qry[i].second.first--;
    qry[i].second.second--;
    qry[i].first.second = i;
  }
  sort(edges + 1, edges + N, greater<pair<int, int> >());
  sort(qry, qry + Q, greater<pair<pair<int, int>, pair<int, int> > >());
  computeSZ(0, -1);
  chain.push_back(Segtree());
  par[0] = -1;
  buildHLD(0, -1);
  chain[0].init();
  int j = 1;
  for (int i = 0; i < Q; i++) {
    for (; j < N && edges[j].first >= qry[i].first.first; j++)
      addEdge(edges[j].second);
    ans[qry[i].first.second] = solve(qry[i].second.first, qry[i].second.second);
  }
  for (int i = 0; i < Q; i++) cout << ans[i] << "\n";
  return 0;
}

```