#include <bits/stdc++.h>
using namespace std;
const int N = 100011;
const int M = 20;
int f[N];
struct Seg {
  int len;
  bool all;
  int l, r;
  int sum;
  Seg() {}
  Seg(int len, bool all, int l, int r, int sum)
      : len(len), all(all), l(l), r(r), sum(sum) {}
  Seg reverse() {
    Seg res = *this;
    swap(res.l, res.r);
    return res;
  }
  Seg merge(const Seg &rhs) {
    Seg res(len + rhs.len, false, 0, 0, sum + rhs.sum);
    if (all && rhs.all)
      res.all = true;
    else if (all) {
      res.l = len + rhs.l;
      res.r = rhs.r;
    } else if (rhs.all) {
      res.l = l;
      res.r = r + rhs.len;
    } else {
      res.l = l;
      res.r = rhs.r;
      res.sum += f[r + rhs.l];
    }
    return res;
  }
  int ans() {
    if (all) return f[len];
    return sum + f[l] + f[r];
  }
};
struct SegTree {
  int l[N << 2];
  int r[N << 2];
  Seg seg[N << 2];
  SegTree() {}
  void init(int left, int right, int x = 1) {
    l[x] = left;
    r[x] = right;
    seg[x] = Seg(right - left, false, 0, 0, 0);
    if (left + 1 < right) {
      int mid = (left + right) / 2;
      init(left, mid, 2 * x);
      init(mid, right, 2 * x + 1);
    }
  }
  void change(int pos, int x = 1) {
    if (l[x] + 1 == r[x])
      seg[x] = Seg(1, true, 0, 0, 0);
    else {
      int mid = (l[x] + r[x]) / 2;
      if (pos < mid)
        change(pos, 2 * x);
      else
        change(pos, 2 * x + 1);
      seg[x] = seg[2 * x].merge(seg[2 * x + 1]);
    }
  }
  Seg query(int left, int right, int x = 1) {
    if (l[x] == left && r[x] == right) return seg[x];
    int mid = (l[x] + r[x]) / 2;
    if (right <= mid)
      return query(left, right, 2 * x);
    else if (left >= mid)
      return query(left, right, 2 * x + 1);
    return query(left, mid, 2 * x).merge(query(mid, right, 2 * x + 1));
  }
} st;
vector<pair<int, int> > edges[N];
int ew[N];
int size[N];
int depth[N];
int heavy_child[N];
int anc[N][M];
void dfs1(int cur, int last = -1) {
  size[cur] = 1;
  for (auto &p : edges[cur])
    if (p.first != last) {
      ew[p.first] = p.second;
      depth[p.first] = depth[cur] + 1;
      anc[p.first][0] = cur;
      dfs1(p.first, cur);
      size[cur] += size[p.first];
    }
  heavy_child[cur] = -1;
  for (auto &p : edges[cur])
    if (p.first != last)
      if (heavy_child[cur] == -1 || size[p.first] > size[heavy_child[cur]])
        heavy_child[cur] = p.first;
}
int top[N];
int nid[N];
void dfs2(int cur, int chain_top, int &cnt, int last = -1) {
  top[cur] = chain_top;
  nid[cur] = ++cnt;
  if (heavy_child[cur] != -1) dfs2(heavy_child[cur], chain_top, cnt, cur);
  for (auto &p : edges[cur])
    if (p.first != last && p.first != heavy_child[cur])
      dfs2(p.first, p.first, cnt, cur);
}
int lca(int u, int v) {
  if (depth[u] > depth[v]) swap(u, v);
  for (int i = M - 1; i >= 0; i--)
    if (depth[anc[v][i]] >= depth[u]) v = anc[v][i];
  if (u == v) return u;
  for (int i = M - 1; i >= 0; i--)
    if (anc[u][i] != anc[v][i]) {
      u = anc[u][i];
      v = anc[v][i];
    }
  return anc[u][0];
}
int ans[N];
struct Event {
  int type;
  int par1;
  int par2;
  Event(int type, int par1, int par2) : type(type), par1(par1), par2(par2) {}
  bool operator<(const Event &rhs) const {
    if (par1 == rhs.par1) return type < rhs.type;
    return par1 > rhs.par1;
  }
};
int u[N], v[N], l[N];
Seg query(int down, int up) {
  bool first = true;
  Seg res;
  while (down != up)
    if (depth[top[down]] > depth[up]) {
      if (first) {
        first = false;
        res = st.query(nid[top[down]], nid[down] + 1);
      } else
        res = st.query(nid[top[down]], nid[down] + 1).merge(res);
      down = anc[top[down]][0];
    } else {
      int tmp = down;
      for (int i = M - 1; i >= 0; i--)
        if (depth[anc[tmp][i]] > depth[up]) tmp = anc[tmp][i];
      if (first) {
        first = false;
        res = st.query(nid[tmp], nid[down] + 1);
      } else
        res = st.query(nid[tmp], nid[down] + 1).merge(res);
      down = anc[tmp][0];
    }
  return res;
}
int main() {
  ios ::sync_with_stdio(false);
  int n, q;
  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;
    edges[u].push_back({v, w});
    edges[v].push_back({u, w});
  }
  dfs1(1);
  int cnt = 0;
  dfs2(1, 1, cnt);
  anc[1][0] = 1;
  for (int j = 1; j < M; j++)
    for (int i = 1; i <= n; i++) anc[i][j] = anc[anc[i][j - 1]][j - 1];
  st.init(1, n + 1);
  vector<Event> events;
  for (int i = 2; i <= n; i++) events.push_back(Event(0, ew[i], i));
  for (int i = 0; i < q; i++) {
    cin >> u[i] >> v[i] >> l[i];
    events.push_back(Event(1, l[i], i));
  }
  sort(events.begin(), events.end());
  for (auto &eve : events)
    if (eve.type == 0)
      st.change(nid[eve.par2]);
    else {
      int qid = eve.par2;
      int up = lca(u[qid], v[qid]);
      if (up == u[qid])
        ans[qid] = query(v[qid], up).ans();
      else if (up == v[qid])
        ans[qid] = query(u[qid], up).ans();
      else
        ans[qid] = (query(u[qid], up).reverse().merge(query(v[qid], up))).ans();
    }
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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 N = 100011;
const int M = 20;
int f[N];
struct Seg {
  int len;
  bool all;
  int l, r;
  int sum;
  Seg() {}
  Seg(int len, bool all, int l, int r, int sum)
      : len(len), all(all), l(l), r(r), sum(sum) {}
  Seg reverse() {
    Seg res = *this;
    swap(res.l, res.r);
    return res;
  }
  Seg merge(const Seg &rhs) {
    Seg res(len + rhs.len, false, 0, 0, sum + rhs.sum);
    if (all && rhs.all)
      res.all = true;
    else if (all) {
      res.l = len + rhs.l;
      res.r = rhs.r;
    } else if (rhs.all) {
      res.l = l;
      res.r = r + rhs.len;
    } else {
      res.l = l;
      res.r = rhs.r;
      res.sum += f[r + rhs.l];
    }
    return res;
  }
  int ans() {
    if (all) return f[len];
    return sum + f[l] + f[r];
  }
};
struct SegTree {
  int l[N << 2];
  int r[N << 2];
  Seg seg[N << 2];
  SegTree() {}
  void init(int left, int right, int x = 1) {
    l[x] = left;
    r[x] = right;
    seg[x] = Seg(right - left, false, 0, 0, 0);
    if (left + 1 < right) {
      int mid = (left + right) / 2;
      init(left, mid, 2 * x);
      init(mid, right, 2 * x + 1);
    }
  }
  void change(int pos, int x = 1) {
    if (l[x] + 1 == r[x])
      seg[x] = Seg(1, true, 0, 0, 0);
    else {
      int mid = (l[x] + r[x]) / 2;
      if (pos < mid)
        change(pos, 2 * x);
      else
        change(pos, 2 * x + 1);
      seg[x] = seg[2 * x].merge(seg[2 * x + 1]);
    }
  }
  Seg query(int left, int right, int x = 1) {
    if (l[x] == left && r[x] == right) return seg[x];
    int mid = (l[x] + r[x]) / 2;
    if (right <= mid)
      return query(left, right, 2 * x);
    else if (left >= mid)
      return query(left, right, 2 * x + 1);
    return query(left, mid, 2 * x).merge(query(mid, right, 2 * x + 1));
  }
} st;
vector<pair<int, int> > edges[N];
int ew[N];
int size[N];
int depth[N];
int heavy_child[N];
int anc[N][M];
void dfs1(int cur, int last = -1) {
  size[cur] = 1;
  for (auto &p : edges[cur])
    if (p.first != last) {
      ew[p.first] = p.second;
      depth[p.first] = depth[cur] + 1;
      anc[p.first][0] = cur;
      dfs1(p.first, cur);
      size[cur] += size[p.first];
    }
  heavy_child[cur] = -1;
  for (auto &p : edges[cur])
    if (p.first != last)
      if (heavy_child[cur] == -1 || size[p.first] > size[heavy_child[cur]])
        heavy_child[cur] = p.first;
}
int top[N];
int nid[N];
void dfs2(int cur, int chain_top, int &cnt, int last = -1) {
  top[cur] = chain_top;
  nid[cur] = ++cnt;
  if (heavy_child[cur] != -1) dfs2(heavy_child[cur], chain_top, cnt, cur);
  for (auto &p : edges[cur])
    if (p.first != last && p.first != heavy_child[cur])
      dfs2(p.first, p.first, cnt, cur);
}
int lca(int u, int v) {
  if (depth[u] > depth[v]) swap(u, v);
  for (int i = M - 1; i >= 0; i--)
    if (depth[anc[v][i]] >= depth[u]) v = anc[v][i];
  if (u == v) return u;
  for (int i = M - 1; i >= 0; i--)
    if (anc[u][i] != anc[v][i]) {
      u = anc[u][i];
      v = anc[v][i];
    }
  return anc[u][0];
}
int ans[N];
struct Event {
  int type;
  int par1;
  int par2;
  Event(int type, int par1, int par2) : type(type), par1(par1), par2(par2) {}
  bool operator<(const Event &rhs) const {
    if (par1 == rhs.par1) return type < rhs.type;
    return par1 > rhs.par1;
  }
};
int u[N], v[N], l[N];
Seg query(int down, int up) {
  bool first = true;
  Seg res;
  while (down != up)
    if (depth[top[down]] > depth[up]) {
      if (first) {
        first = false;
        res = st.query(nid[top[down]], nid[down] + 1);
      } else
        res = st.query(nid[top[down]], nid[down] + 1).merge(res);
      down = anc[top[down]][0];
    } else {
      int tmp = down;
      for (int i = M - 1; i >= 0; i--)
        if (depth[anc[tmp][i]] > depth[up]) tmp = anc[tmp][i];
      if (first) {
        first = false;
        res = st.query(nid[tmp], nid[down] + 1);
      } else
        res = st.query(nid[tmp], nid[down] + 1).merge(res);
      down = anc[tmp][0];
    }
  return res;
}
int main() {
  ios ::sync_with_stdio(false);
  int n, q;
  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;
    edges[u].push_back({v, w});
    edges[v].push_back({u, w});
  }
  dfs1(1);
  int cnt = 0;
  dfs2(1, 1, cnt);
  anc[1][0] = 1;
  for (int j = 1; j < M; j++)
    for (int i = 1; i <= n; i++) anc[i][j] = anc[anc[i][j - 1]][j - 1];
  st.init(1, n + 1);
  vector<Event> events;
  for (int i = 2; i <= n; i++) events.push_back(Event(0, ew[i], i));
  for (int i = 0; i < q; i++) {
    cin >> u[i] >> v[i] >> l[i];
    events.push_back(Event(1, l[i], i));
  }
  sort(events.begin(), events.end());
  for (auto &eve : events)
    if (eve.type == 0)
      st.change(nid[eve.par2]);
    else {
      int qid = eve.par2;
      int up = lca(u[qid], v[qid]);
      if (up == u[qid])
        ans[qid] = query(v[qid], up).ans();
      else if (up == v[qid])
        ans[qid] = query(u[qid], up).ans();
      else
        ans[qid] = (query(u[qid], up).reverse().merge(query(v[qid], up))).ans();
    }
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
  return 0;
}

```