#include <bits/stdc++.h>
using namespace std;
template <class T>
bool setmax(T &_a, T _b) {
  if (_b > _a) {
    _a = _b;
    return true;
  }
  return false;
}
template <class T>
bool setmin(T &_a, T _b) {
  if (_b < _a) {
    _a = _b;
    return true;
  }
  return false;
}
template <class T>
T gcd(T _a, T _b) {
  return _b == 0 ? _a : gcd(_b, _a % _b);
}
const int MAXN = 100010;
const int MAXQ = 100010;
const int MAXLog = 20;
int g[MAXN], g_lnk[MAXN * 2], g_cst[MAXN * 2], g_nxt[MAXN * 2];
struct Query {
  int u, v, l, i;
} queries[MAXQ];
int f[MAXN];
int n, q;
void init() {
  scanf("%d%d", &n, &q);
  for (int i = int(1); i <= int(n - 1); ++i) scanf("%d", &f[i]);
  memset(g, 0, sizeof(g));
  int e = 0;
  for (int i = int(1); i <= int(n - 1); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    g_lnk[++e] = b, g_cst[e] = c, g_nxt[e] = g[a], g[a] = e;
    g_lnk[++e] = a, g_cst[e] = c, g_nxt[e] = g[b], g[b] = e;
  }
  for (int i = int(1); i <= int(q); ++i) {
    scanf("%d%d%d", &queries[i].u, &queries[i].v, &queries[i].l);
    queries[i].i = i;
  }
}
int the[MAXN], dep[MAXN], size[MAXN], up[MAXN][MAXLog];
void dfs0(int x, int fa) {
  dep[x] = dep[fa] + 1;
  size[x] = 1;
  memset(up[x], 0, sizeof(up[x]));
  up[x][0] = fa;
  for (int i = 0; up[x][i] > 0; ++i) up[x][i + 1] = up[up[x][i]][i];
  for (int e = g[x]; e; e = g_nxt[e]) {
    int y = g_lnk[e];
    if (y != fa) {
      dfs0(y, x);
      size[x] += size[y];
      the[y] = g_cst[e];
    }
  }
}
int go_up(int x, int d) {
  for (int i = int(0); i <= int((MAXLog)-1); ++i)
    if (d & (1 << i)) x = up[x][i];
  return x;
}
int lca(int x, int y) {
  {};
  for (int i = int((MAXLog)-1); i >= int(0); --i) {
    if (dep[up[x][i]] >= dep[y]) x = up[x][i];
    if (dep[up[y][i]] >= dep[x]) y = up[y][i];
  }
  for (int i = int((MAXLog)-1); i >= int(0); --i) {
    if (up[x][i] != up[y][i]) {
      x = up[x][i];
      y = up[y][i];
    }
  }
  if (x != y) {
    x = up[x][0];
    y = up[y][0];
  }
  assert(x == y);
  assert(x != 0);
  return x;
}
int ind[MAXN], head[MAXN], num;
void dfs(int x, int fa) {
  int ymax = 0;
  for (int e = g[x]; e; e = g_nxt[e]) {
    int y = g_lnk[e];
    if (y != fa && size[y] > size[ymax]) ymax = y;
  }
  for (int e = g[x]; e; e = g_nxt[e]) {
    int y = g_lnk[e];
    if (y != fa && y != ymax) dfs(y, x);
  }
  if (ymax > 0) {
    head[ymax] = head[x];
    dfs(ymax, x);
    assert(ind[ymax] == num);
  }
  ind[x] = ++num;
}
void preprocess() {
  memset(up[0], 0, sizeof(up[0]));
  dep[0] = size[0] = 0;
  the[1] = 0;
  dfs0(1, 0);
  for (int i = int(1); i <= int(n); ++i) head[i] = i;
  num = 0;
  dfs(1, 0);
  assert(num == n);
}
struct St {
  bool pure;
  int l, r, s;
  St() : pure(true), l(0), r(0), s(0) {}
  friend St st_concat(St a, St b) {
    St c;
    if (a.pure && b.pure) {
      assert(a.l == a.r);
      assert(a.s == 0);
      assert(b.l == b.r);
      assert(b.s == 0);
      c.pure = true;
      c.l = c.r = a.l + b.l;
      c.s = 0;
      return c;
    }
    c.pure = false;
    if (a.pure) {
      c.l = a.l + b.l;
      c.r = b.r;
      c.s = b.s;
      return c;
    }
    if (b.pure) {
      c.l = a.l;
      c.r = a.r + b.r;
      c.s = a.s;
      return c;
    }
    c.l = a.l;
    c.r = b.r;
    c.s = a.s + b.s + f[a.r + b.l];
    return c;
  }
  St reverse() const {
    St c = *this;
    swap(c.l, c.r);
    return c;
  }
};
struct Tree {
  St tr[MAXN * 4];
  void init() {
    for (int i = int(0); i <= int((MAXN * 4) - 1); ++i) {
      tr[i] = St();
      tr[i].pure = false;
    }
  }
  void set(int x, int s, int t, int i) {
    if (s == t) {
      tr[x].pure = true;
      tr[x].l = tr[x].r = 1;
      tr[x].s = 0;
      return;
    }
    int mid = (s + t) / 2;
    if (i <= mid)
      set(x * 2, s, mid, i);
    else
      set(x * 2 + 1, mid + 1, t, i);
    tr[x] = st_concat(tr[x * 2], tr[x * 2 + 1]);
  }
  void set(int i) { set(1, 1, n, i); }
  St get(int x, int s, int t, int st, int en) {
    if (st <= s && t <= en) return tr[x];
    int mid = (s + t) / 2;
    St ans;
    if (st <= mid) ans = st_concat(ans, get(x * 2, s, mid, st, en));
    if (mid < en) ans = st_concat(ans, get(x * 2 + 1, mid + 1, t, st, en));
    return ans;
  }
  St get(int l, int r) { return get(1, 1, n, l, r); }
} tree;
St get_straight(int x, int y) {
  {};
  St st;
  assert(dep[x] >= dep[y]);
  while (dep[x] > dep[y]) {
    int z = head[x];
    if (dep[z] > dep[y]) {
      {};
      St tmp = tree.get(ind[x], ind[z]);
      st = st_concat(st, tmp);
      x = up[z][0];
    } else {
      {};
      St tmp = tree.get(ind[x], ind[y] - 1);
      st = st_concat(st, tmp);
      x = y;
    }
  }
  assert(x == y);
  return st;
}
int answer(int x, int y) {
  int z = lca(x, y);
  St sx = get_straight(x, z);
  St sy = get_straight(y, z).reverse();
  St s = st_concat(sx, sy);
  {};
  int ans = s.s;
  ans += f[s.l];
  if (!s.pure) ans += f[s.r];
  return ans;
}
void solve() {
  {};
  static pair<int, int> keys[MAXN];
  for (int i = int(1); i <= int(n); ++i) keys[i] = make_pair(the[i], i);
  sort(keys + 1, keys + n + 1, greater<pair<int, int> >());
  {};
  static int ans[MAXQ];
  sort(queries + 1, queries + q + 1,
       [](const Query &a, const Query &b) -> bool { return a.l > b.l; });
  int cur = 1;
  tree.init();
  for (int j = int(1); j <= int(q); ++j) {
    {};
    while (cur <= n && keys[cur].first >= queries[j].l) {
      {};
      tree.set(ind[keys[cur].second]);
      ++cur;
    }
    ans[queries[j].i] = answer(queries[j].u, queries[j].v);
  }
  for (int i = int(1); i <= int(q); ++i) printf("%d\n", ans[i]);
}
int main() {
  init();
  preprocess();
  solve();
  return 0;
}

### Prompt

Please provide a cpp coded solution 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;
template <class T>
bool setmax(T &_a, T _b) {
  if (_b > _a) {
    _a = _b;
    return true;
  }
  return false;
}
template <class T>
bool setmin(T &_a, T _b) {
  if (_b < _a) {
    _a = _b;
    return true;
  }
  return false;
}
template <class T>
T gcd(T _a, T _b) {
  return _b == 0 ? _a : gcd(_b, _a % _b);
}
const int MAXN = 100010;
const int MAXQ = 100010;
const int MAXLog = 20;
int g[MAXN], g_lnk[MAXN * 2], g_cst[MAXN * 2], g_nxt[MAXN * 2];
struct Query {
  int u, v, l, i;
} queries[MAXQ];
int f[MAXN];
int n, q;
void init() {
  scanf("%d%d", &n, &q);
  for (int i = int(1); i <= int(n - 1); ++i) scanf("%d", &f[i]);
  memset(g, 0, sizeof(g));
  int e = 0;
  for (int i = int(1); i <= int(n - 1); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    g_lnk[++e] = b, g_cst[e] = c, g_nxt[e] = g[a], g[a] = e;
    g_lnk[++e] = a, g_cst[e] = c, g_nxt[e] = g[b], g[b] = e;
  }
  for (int i = int(1); i <= int(q); ++i) {
    scanf("%d%d%d", &queries[i].u, &queries[i].v, &queries[i].l);
    queries[i].i = i;
  }
}
int the[MAXN], dep[MAXN], size[MAXN], up[MAXN][MAXLog];
void dfs0(int x, int fa) {
  dep[x] = dep[fa] + 1;
  size[x] = 1;
  memset(up[x], 0, sizeof(up[x]));
  up[x][0] = fa;
  for (int i = 0; up[x][i] > 0; ++i) up[x][i + 1] = up[up[x][i]][i];
  for (int e = g[x]; e; e = g_nxt[e]) {
    int y = g_lnk[e];
    if (y != fa) {
      dfs0(y, x);
      size[x] += size[y];
      the[y] = g_cst[e];
    }
  }
}
int go_up(int x, int d) {
  for (int i = int(0); i <= int((MAXLog)-1); ++i)
    if (d & (1 << i)) x = up[x][i];
  return x;
}
int lca(int x, int y) {
  {};
  for (int i = int((MAXLog)-1); i >= int(0); --i) {
    if (dep[up[x][i]] >= dep[y]) x = up[x][i];
    if (dep[up[y][i]] >= dep[x]) y = up[y][i];
  }
  for (int i = int((MAXLog)-1); i >= int(0); --i) {
    if (up[x][i] != up[y][i]) {
      x = up[x][i];
      y = up[y][i];
    }
  }
  if (x != y) {
    x = up[x][0];
    y = up[y][0];
  }
  assert(x == y);
  assert(x != 0);
  return x;
}
int ind[MAXN], head[MAXN], num;
void dfs(int x, int fa) {
  int ymax = 0;
  for (int e = g[x]; e; e = g_nxt[e]) {
    int y = g_lnk[e];
    if (y != fa && size[y] > size[ymax]) ymax = y;
  }
  for (int e = g[x]; e; e = g_nxt[e]) {
    int y = g_lnk[e];
    if (y != fa && y != ymax) dfs(y, x);
  }
  if (ymax > 0) {
    head[ymax] = head[x];
    dfs(ymax, x);
    assert(ind[ymax] == num);
  }
  ind[x] = ++num;
}
void preprocess() {
  memset(up[0], 0, sizeof(up[0]));
  dep[0] = size[0] = 0;
  the[1] = 0;
  dfs0(1, 0);
  for (int i = int(1); i <= int(n); ++i) head[i] = i;
  num = 0;
  dfs(1, 0);
  assert(num == n);
}
struct St {
  bool pure;
  int l, r, s;
  St() : pure(true), l(0), r(0), s(0) {}
  friend St st_concat(St a, St b) {
    St c;
    if (a.pure && b.pure) {
      assert(a.l == a.r);
      assert(a.s == 0);
      assert(b.l == b.r);
      assert(b.s == 0);
      c.pure = true;
      c.l = c.r = a.l + b.l;
      c.s = 0;
      return c;
    }
    c.pure = false;
    if (a.pure) {
      c.l = a.l + b.l;
      c.r = b.r;
      c.s = b.s;
      return c;
    }
    if (b.pure) {
      c.l = a.l;
      c.r = a.r + b.r;
      c.s = a.s;
      return c;
    }
    c.l = a.l;
    c.r = b.r;
    c.s = a.s + b.s + f[a.r + b.l];
    return c;
  }
  St reverse() const {
    St c = *this;
    swap(c.l, c.r);
    return c;
  }
};
struct Tree {
  St tr[MAXN * 4];
  void init() {
    for (int i = int(0); i <= int((MAXN * 4) - 1); ++i) {
      tr[i] = St();
      tr[i].pure = false;
    }
  }
  void set(int x, int s, int t, int i) {
    if (s == t) {
      tr[x].pure = true;
      tr[x].l = tr[x].r = 1;
      tr[x].s = 0;
      return;
    }
    int mid = (s + t) / 2;
    if (i <= mid)
      set(x * 2, s, mid, i);
    else
      set(x * 2 + 1, mid + 1, t, i);
    tr[x] = st_concat(tr[x * 2], tr[x * 2 + 1]);
  }
  void set(int i) { set(1, 1, n, i); }
  St get(int x, int s, int t, int st, int en) {
    if (st <= s && t <= en) return tr[x];
    int mid = (s + t) / 2;
    St ans;
    if (st <= mid) ans = st_concat(ans, get(x * 2, s, mid, st, en));
    if (mid < en) ans = st_concat(ans, get(x * 2 + 1, mid + 1, t, st, en));
    return ans;
  }
  St get(int l, int r) { return get(1, 1, n, l, r); }
} tree;
St get_straight(int x, int y) {
  {};
  St st;
  assert(dep[x] >= dep[y]);
  while (dep[x] > dep[y]) {
    int z = head[x];
    if (dep[z] > dep[y]) {
      {};
      St tmp = tree.get(ind[x], ind[z]);
      st = st_concat(st, tmp);
      x = up[z][0];
    } else {
      {};
      St tmp = tree.get(ind[x], ind[y] - 1);
      st = st_concat(st, tmp);
      x = y;
    }
  }
  assert(x == y);
  return st;
}
int answer(int x, int y) {
  int z = lca(x, y);
  St sx = get_straight(x, z);
  St sy = get_straight(y, z).reverse();
  St s = st_concat(sx, sy);
  {};
  int ans = s.s;
  ans += f[s.l];
  if (!s.pure) ans += f[s.r];
  return ans;
}
void solve() {
  {};
  static pair<int, int> keys[MAXN];
  for (int i = int(1); i <= int(n); ++i) keys[i] = make_pair(the[i], i);
  sort(keys + 1, keys + n + 1, greater<pair<int, int> >());
  {};
  static int ans[MAXQ];
  sort(queries + 1, queries + q + 1,
       [](const Query &a, const Query &b) -> bool { return a.l > b.l; });
  int cur = 1;
  tree.init();
  for (int j = int(1); j <= int(q); ++j) {
    {};
    while (cur <= n && keys[cur].first >= queries[j].l) {
      {};
      tree.set(ind[keys[cur].second]);
      ++cur;
    }
    ans[queries[j].i] = answer(queries[j].u, queries[j].v);
  }
  for (int i = int(1); i <= int(q); ++i) printf("%d\n", ans[i]);
}
int main() {
  init();
  preprocess();
  solve();
  return 0;
}

```