#include <bits/stdc++.h>
using namespace std;
template <class T>
bool uin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool uax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
const int MAXN = 200000;
const int LOG = 20;
int f[MAXN];
struct TResult {
  int l1, r1;
  int sum;
  bool f1;
  TResult(int l1, int r1, int sum, bool f1)
      : l1(l1), r1(r1), sum(sum), f1(f1) {}
  TResult(int x = 1) : l1(x), r1(x), sum(0), f1(x) {}
  TResult operator+(const TResult &res) const {
    int ll1 = l1, rr1 = res.r1;
    if (f1) ll1 += res.l1;
    if (res.f1) rr1 += r1;
    int ssum = sum + res.sum;
    if (!f1 && !res.f1) ssum += f[r1 + res.l1];
    return TResult(ll1, rr1, ssum, f1 && res.f1);
  }
  TResult sw() const { return TResult(r1, l1, sum, f1); }
};
struct TNode {
  int L, R;
  int left, right;
  TResult res;
  TNode(int L = -1, int R = -1) : L(L), R(R), left(0), right(0), res() {}
};
const int MAXT = 2000000;
TNode t[MAXT];
int tc = 1;
int buildTree(int L, int R) {
  int node = tc++;
  t[node] = TNode(L, R);
  TNode &n = t[node];
  if (R - L > 1) {
    int M = (L + R) / 2;
    n.left = buildTree(L, M);
    n.right = buildTree(M, R);
    n.res = t[n.left].res + t[n.right].res;
  }
  return node;
}
TResult query(int node, int L, int R) {
  TNode &n = t[node];
  if (max(L, n.L) >= min(R, n.R)) return TResult(0, 0, 0, true);
  if (L <= n.L && n.R <= R) return n.res;
  return query(n.left, L, R) + query(n.right, L, R);
}
int sset(int node, int i, int x) {
  if (i < t[node].L || i >= t[node].R) return node;
  int nnode = tc++;
  TNode &n = t[nnode];
  n = t[node];
  if (i == n.L && i + 1 == n.R) {
    n.res = TResult(x);
    return nnode;
  }
  n.left = sset(n.left, i, x);
  n.right = sset(n.right, i, x);
  n.res = t[n.left].res + t[n.right].res;
  return nnode;
}
vector<pair<int, int> > e[MAXN];
int up[LOG + 1][MAXN], par[MAXN];
int sz[MAXN], root[MAXN], rpos[MAXN];
int h[MAXN];
vector<pair<int, int> > tr[MAXN];
void dfs_build(int v, int p) {
  par[v] = p;
  sz[v] = 1;
  for (pair<int, int> w : e[v]) {
    if (w.first == p) continue;
    int u = w.first;
    h[u] = h[v] + 1;
    dfs_build(u, v);
    sz[v] += sz[u];
  }
}
void dfs_sroot(int v, int p) {
  rpos[v] = 0;
  for (pair<int, int> w : e[v]) {
    int u = w.first;
    if (u == p) continue;
    root[u] = (2 * sz[u] >= sz[v] ? root[v] : u);
    dfs_sroot(u, v);
    if (root[u] == root[v]) rpos[v] = rpos[u] + 1;
  }
}
int get_up(int v, int d) {
  for (int i = (int)(LOG + 1) - 1; i >= 0; --i) {
    if ((1 << i) <= d) {
      d -= (1 << i);
      v = up[i][v];
    }
  }
  return v;
}
int lca(int v, int u) {
  if (h[v] < h[u]) swap(v, u);
  v = get_up(v, h[v] - h[u]);
  if (v == u) return v;
  for (int i = (int)(LOG + 1) - 1; i >= 0; --i) {
    if (up[i][u] != up[i][v]) {
      u = up[i][u];
      v = up[i][v];
    }
  }
  return par[u];
}
int get_ver(int r, int w) {
  return (--lower_bound((tr[r]).begin(), (tr[r]).end(), make_pair(w, -1)))
      ->second;
}
TResult hld_res(int v, int w, int d) {
  int r = root[v];
  int ver = get_ver(r, w);
  TResult res = query(ver, rpos[v], min(rpos[v] + d, rpos[r] + 1));
  int dd = d - (rpos[r] - rpos[v] + 1);
  if (dd > 0) res = res + hld_res(par[r], w, dd);
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;
  int N, Q;
  cin >> N >> Q;
  for (int i = 1; i <= (int)(N - 1); ++i) cin >> f[i];
  for (int i = 0; i < (int)(N - 1); ++i) {
    int x, y, w;
    cin >> x >> y >> w;
    --x;
    --y;
    e[x].push_back(make_pair(y, w));
    e[y].push_back(make_pair(x, w));
  }
  dfs_build(0, 0);
  dfs_sroot(0, 0);
  for (int i = 0; i < (int)(N); ++i) {
    if (root[i] == i) tr[i].push_back(make_pair(0, buildTree(0, rpos[i] + 1)));
  }
  for (int i = 0; i < (int)(N); ++i) up[0][i] = par[i];
  for (int i = 1; i <= (int)(LOG); ++i)
    for (int j = 0; j < (int)(N); ++j) {
      up[i][j] = up[i - 1][up[i - 1][j]];
    }
  vector<pair<int, int> > s;
  for (int x = 0; x < (int)(N); ++x) {
    for (pair<int, int> w : e[x]) {
      if (h[x] < h[w.first]) continue;
      s.push_back(make_pair(w.second, x));
    }
  }
  sort((s).begin(), (s).end());
  for (pair<int, int> ch : s) {
    int x = ch.second, w = ch.first;
    int r = root[x];
    int tt = tr[r].back().second;
    tr[r].push_back(make_pair(w, sset(tt, rpos[x], 0)));
  }
  for (int q = 0; q < (int)(Q); ++q) {
    int x, y, l;
    cin >> x >> y >> l;
    --x;
    --y;
    int w = lca(x, y);
    TResult res = hld_res(x, l, h[x] - h[w]) + hld_res(y, l, h[y] - h[w]).sw();
    int ans = res.sum;
    if (res.f1)
      ans += f[res.l1];
    else
      ans += f[res.l1] + f[res.r1];
    cout << ans << '\n';
  }
  return 0;
}

### Prompt

Please create a solution in cpp 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;
template <class T>
bool uin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool uax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
const int MAXN = 200000;
const int LOG = 20;
int f[MAXN];
struct TResult {
  int l1, r1;
  int sum;
  bool f1;
  TResult(int l1, int r1, int sum, bool f1)
      : l1(l1), r1(r1), sum(sum), f1(f1) {}
  TResult(int x = 1) : l1(x), r1(x), sum(0), f1(x) {}
  TResult operator+(const TResult &res) const {
    int ll1 = l1, rr1 = res.r1;
    if (f1) ll1 += res.l1;
    if (res.f1) rr1 += r1;
    int ssum = sum + res.sum;
    if (!f1 && !res.f1) ssum += f[r1 + res.l1];
    return TResult(ll1, rr1, ssum, f1 && res.f1);
  }
  TResult sw() const { return TResult(r1, l1, sum, f1); }
};
struct TNode {
  int L, R;
  int left, right;
  TResult res;
  TNode(int L = -1, int R = -1) : L(L), R(R), left(0), right(0), res() {}
};
const int MAXT = 2000000;
TNode t[MAXT];
int tc = 1;
int buildTree(int L, int R) {
  int node = tc++;
  t[node] = TNode(L, R);
  TNode &n = t[node];
  if (R - L > 1) {
    int M = (L + R) / 2;
    n.left = buildTree(L, M);
    n.right = buildTree(M, R);
    n.res = t[n.left].res + t[n.right].res;
  }
  return node;
}
TResult query(int node, int L, int R) {
  TNode &n = t[node];
  if (max(L, n.L) >= min(R, n.R)) return TResult(0, 0, 0, true);
  if (L <= n.L && n.R <= R) return n.res;
  return query(n.left, L, R) + query(n.right, L, R);
}
int sset(int node, int i, int x) {
  if (i < t[node].L || i >= t[node].R) return node;
  int nnode = tc++;
  TNode &n = t[nnode];
  n = t[node];
  if (i == n.L && i + 1 == n.R) {
    n.res = TResult(x);
    return nnode;
  }
  n.left = sset(n.left, i, x);
  n.right = sset(n.right, i, x);
  n.res = t[n.left].res + t[n.right].res;
  return nnode;
}
vector<pair<int, int> > e[MAXN];
int up[LOG + 1][MAXN], par[MAXN];
int sz[MAXN], root[MAXN], rpos[MAXN];
int h[MAXN];
vector<pair<int, int> > tr[MAXN];
void dfs_build(int v, int p) {
  par[v] = p;
  sz[v] = 1;
  for (pair<int, int> w : e[v]) {
    if (w.first == p) continue;
    int u = w.first;
    h[u] = h[v] + 1;
    dfs_build(u, v);
    sz[v] += sz[u];
  }
}
void dfs_sroot(int v, int p) {
  rpos[v] = 0;
  for (pair<int, int> w : e[v]) {
    int u = w.first;
    if (u == p) continue;
    root[u] = (2 * sz[u] >= sz[v] ? root[v] : u);
    dfs_sroot(u, v);
    if (root[u] == root[v]) rpos[v] = rpos[u] + 1;
  }
}
int get_up(int v, int d) {
  for (int i = (int)(LOG + 1) - 1; i >= 0; --i) {
    if ((1 << i) <= d) {
      d -= (1 << i);
      v = up[i][v];
    }
  }
  return v;
}
int lca(int v, int u) {
  if (h[v] < h[u]) swap(v, u);
  v = get_up(v, h[v] - h[u]);
  if (v == u) return v;
  for (int i = (int)(LOG + 1) - 1; i >= 0; --i) {
    if (up[i][u] != up[i][v]) {
      u = up[i][u];
      v = up[i][v];
    }
  }
  return par[u];
}
int get_ver(int r, int w) {
  return (--lower_bound((tr[r]).begin(), (tr[r]).end(), make_pair(w, -1)))
      ->second;
}
TResult hld_res(int v, int w, int d) {
  int r = root[v];
  int ver = get_ver(r, w);
  TResult res = query(ver, rpos[v], min(rpos[v] + d, rpos[r] + 1));
  int dd = d - (rpos[r] - rpos[v] + 1);
  if (dd > 0) res = res + hld_res(par[r], w, dd);
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;
  int N, Q;
  cin >> N >> Q;
  for (int i = 1; i <= (int)(N - 1); ++i) cin >> f[i];
  for (int i = 0; i < (int)(N - 1); ++i) {
    int x, y, w;
    cin >> x >> y >> w;
    --x;
    --y;
    e[x].push_back(make_pair(y, w));
    e[y].push_back(make_pair(x, w));
  }
  dfs_build(0, 0);
  dfs_sroot(0, 0);
  for (int i = 0; i < (int)(N); ++i) {
    if (root[i] == i) tr[i].push_back(make_pair(0, buildTree(0, rpos[i] + 1)));
  }
  for (int i = 0; i < (int)(N); ++i) up[0][i] = par[i];
  for (int i = 1; i <= (int)(LOG); ++i)
    for (int j = 0; j < (int)(N); ++j) {
      up[i][j] = up[i - 1][up[i - 1][j]];
    }
  vector<pair<int, int> > s;
  for (int x = 0; x < (int)(N); ++x) {
    for (pair<int, int> w : e[x]) {
      if (h[x] < h[w.first]) continue;
      s.push_back(make_pair(w.second, x));
    }
  }
  sort((s).begin(), (s).end());
  for (pair<int, int> ch : s) {
    int x = ch.second, w = ch.first;
    int r = root[x];
    int tt = tr[r].back().second;
    tr[r].push_back(make_pair(w, sset(tt, rpos[x], 0)));
  }
  for (int q = 0; q < (int)(Q); ++q) {
    int x, y, l;
    cin >> x >> y >> l;
    --x;
    --y;
    int w = lca(x, y);
    TResult res = hld_res(x, l, h[x] - h[w]) + hld_res(y, l, h[y] - h[w]).sw();
    int ans = res.sum;
    if (res.f1)
      ans += f[res.l1];
    else
      ans += f[res.l1] + f[res.r1];
    cout << ans << '\n';
  }
  return 0;
}

```