#include <bits/stdc++.h>
using namespace std;
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << "{";
  for (const T &a : v) out << a << ", ";
  out << "}";
  return out;
}
template <typename S, typename T>
ostream &operator<<(ostream &out, const pair<S, T> &p) {
  out << "(" << p.first << ", " << p.second << ")";
  return out;
}
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
const int MAXN = 100010;
int F[MAXN];
struct path {
  int pref, total, suf, len;
  path() : pref(0), total(0), suf(0), len(1) {}
  path(int a, int b, int c, int d) : pref(a), total(b), suf(c), len(d) {}
  path(int a) : pref(a), total(0), suf(a), len(a) {}
};
path merge(path a, path b) {
  if (a.pref == a.len && b.pref == b.len) return path(a.len + b.len);
  if (a.pref == a.len)
    return path(a.pref + b.pref, b.total, b.suf, a.len + b.len);
  if (b.pref == b.len)
    return path(a.pref, a.total, a.suf + b.pref, a.len + b.len);
  return path(a.pref, a.total + F[a.suf + b.pref] + b.total, b.suf,
              a.len + b.len);
}
path reverse(path a) { return path(a.suf, a.total, a.pref, a.len); }
int eval(path a) {
  if (a.pref == a.len) return F[a.len];
  return F[a.pref] + a.total + F[a.suf];
}
struct tree {
  int n, d;
  vector<path> data;
  tree() : n(0) {}
  void init() {
    d = 1;
    while (d < n) d *= 2;
    data.resize(2 * d);
  }
  void lit(int first) {
    first += d;
    data[first] = path(1);
    first /= 2;
    while (first) {
      data[first] = merge(data[2 * first], data[2 * first + 1]);
      first /= 2;
    }
  }
  path get(int a, int b) {
    assert(max(a, b) < n);
    a += d;
    b += d;
    path pref(0), suf(0);
    while (a < b) {
      if (a & 1) {
        pref = merge(pref, data[a]);
        ++a;
      }
      if ((b & 1) == 0) {
        suf = merge(data[b], suf);
        --b;
      }
      a /= 2;
      b /= 2;
    }
    if (a == b) pref = merge(pref, data[a]);
    return merge(pref, suf);
  }
};
int I[MAXN];
int J[MAXN];
int R[MAXN];
vector<tree> HLD;
vector<pair<int, int> > edges[MAXN];
bool vis[MAXN];
int size[MAXN];
int depth[MAXN];
pair<int, int> parent[MAXN];
void dfs(int u) {
  vis[u] = 1;
  size[u] = 1;
  int b = -1;
  for (pair<int, int> e : edges[u])
    if (!vis[e.first]) {
      parent[e.first] = pair<int, int>(u, e.second);
      depth[e.first] = depth[u] + 1;
      dfs(e.first);
      size[u] += size[e.first];
      if (b == -1 || size[b] < size[e.first]) b = e.first;
    }
  if (b == -1) {
    I[u] = ((int)(HLD).size());
    HLD.push_back(tree());
  } else
    I[u] = I[b];
  R[I[u]] = u;
  ++HLD[I[u]].n;
  vis[u] = 0;
}
vector<pair<int, int> > mods;
void init(int u) {
  vis[u] = 1;
  if (R[I[u]] == u) {
    J[u] = 0;
    HLD[I[u]].init();
  } else
    J[u] = J[parent[u].first] + 1;
  if (u > 1) mods.push_back(pair<int, int>(parent[u].second, u));
  for (pair<int, int> e : edges[u])
    if (!vis[e.first]) init(e.first);
  vis[u] = 0;
}
int n, q;
vector<pair<int, int> > queries;
int A[MAXN], B[MAXN];
int res[MAXN];
int main() {
  scanf("%d %d", &n, &q);
  for (int i = (1); i < (n); ++i) scanf("%d", &F[i]);
  for (int i = (1); i < (n); ++i) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    edges[a].push_back(pair<int, int>(b, c));
    edges[b].push_back(pair<int, int>(a, c));
  }
  dfs(1);
  init(1);
  for (int i = (0); i < (q); ++i) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    A[i] = a;
    B[i] = b;
    queries.push_back(pair<int, int>(c, i));
  }
  sort((mods).begin(), (mods).end(), greater<pair<int, int> >());
  sort((queries).begin(), (queries).end(), greater<pair<int, int> >());
  q = 0;
  int m = 0;
  while (q < ((int)(queries).size())) {
    while (m < ((int)(mods).size()) && mods[m].first >= queries[q].first) {
      int u = mods[m].second;
      HLD[I[u]].lit(J[u]);
      ++m;
    }
    int u = B[queries[q].second];
    int v = A[queries[q].second];
    path tu, tv;
    while (I[u] != I[v]) {
      if (depth[R[I[u]]] > depth[R[I[v]]]) {
        tu = merge(HLD[I[u]].get(0, J[u]), tu);
        u = parent[R[I[u]]].first;
      } else {
        tv = merge(HLD[I[v]].get(0, J[v]), tv);
        v = parent[R[I[v]]].first;
      }
    }
    if (J[u] < J[v]) {
      tu = merge(reverse(tu), HLD[I[u]].get(J[u] + 1, J[v]));
      tu = merge(tu, tv);
    } else {
      tv = merge(reverse(tv), HLD[I[u]].get(J[v] + 1, J[u]));
      tu = merge(tv, tu);
    }
    res[queries[q].second] = eval(tu);
    ++q;
  }
  for (int i = (0); i < (q); ++i) printf("%d\n", res[i]);
  return 0;
}

### Prompt

Your challenge is to write a cpp solution 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 <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << "{";
  for (const T &a : v) out << a << ", ";
  out << "}";
  return out;
}
template <typename S, typename T>
ostream &operator<<(ostream &out, const pair<S, T> &p) {
  out << "(" << p.first << ", " << p.second << ")";
  return out;
}
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
const int MAXN = 100010;
int F[MAXN];
struct path {
  int pref, total, suf, len;
  path() : pref(0), total(0), suf(0), len(1) {}
  path(int a, int b, int c, int d) : pref(a), total(b), suf(c), len(d) {}
  path(int a) : pref(a), total(0), suf(a), len(a) {}
};
path merge(path a, path b) {
  if (a.pref == a.len && b.pref == b.len) return path(a.len + b.len);
  if (a.pref == a.len)
    return path(a.pref + b.pref, b.total, b.suf, a.len + b.len);
  if (b.pref == b.len)
    return path(a.pref, a.total, a.suf + b.pref, a.len + b.len);
  return path(a.pref, a.total + F[a.suf + b.pref] + b.total, b.suf,
              a.len + b.len);
}
path reverse(path a) { return path(a.suf, a.total, a.pref, a.len); }
int eval(path a) {
  if (a.pref == a.len) return F[a.len];
  return F[a.pref] + a.total + F[a.suf];
}
struct tree {
  int n, d;
  vector<path> data;
  tree() : n(0) {}
  void init() {
    d = 1;
    while (d < n) d *= 2;
    data.resize(2 * d);
  }
  void lit(int first) {
    first += d;
    data[first] = path(1);
    first /= 2;
    while (first) {
      data[first] = merge(data[2 * first], data[2 * first + 1]);
      first /= 2;
    }
  }
  path get(int a, int b) {
    assert(max(a, b) < n);
    a += d;
    b += d;
    path pref(0), suf(0);
    while (a < b) {
      if (a & 1) {
        pref = merge(pref, data[a]);
        ++a;
      }
      if ((b & 1) == 0) {
        suf = merge(data[b], suf);
        --b;
      }
      a /= 2;
      b /= 2;
    }
    if (a == b) pref = merge(pref, data[a]);
    return merge(pref, suf);
  }
};
int I[MAXN];
int J[MAXN];
int R[MAXN];
vector<tree> HLD;
vector<pair<int, int> > edges[MAXN];
bool vis[MAXN];
int size[MAXN];
int depth[MAXN];
pair<int, int> parent[MAXN];
void dfs(int u) {
  vis[u] = 1;
  size[u] = 1;
  int b = -1;
  for (pair<int, int> e : edges[u])
    if (!vis[e.first]) {
      parent[e.first] = pair<int, int>(u, e.second);
      depth[e.first] = depth[u] + 1;
      dfs(e.first);
      size[u] += size[e.first];
      if (b == -1 || size[b] < size[e.first]) b = e.first;
    }
  if (b == -1) {
    I[u] = ((int)(HLD).size());
    HLD.push_back(tree());
  } else
    I[u] = I[b];
  R[I[u]] = u;
  ++HLD[I[u]].n;
  vis[u] = 0;
}
vector<pair<int, int> > mods;
void init(int u) {
  vis[u] = 1;
  if (R[I[u]] == u) {
    J[u] = 0;
    HLD[I[u]].init();
  } else
    J[u] = J[parent[u].first] + 1;
  if (u > 1) mods.push_back(pair<int, int>(parent[u].second, u));
  for (pair<int, int> e : edges[u])
    if (!vis[e.first]) init(e.first);
  vis[u] = 0;
}
int n, q;
vector<pair<int, int> > queries;
int A[MAXN], B[MAXN];
int res[MAXN];
int main() {
  scanf("%d %d", &n, &q);
  for (int i = (1); i < (n); ++i) scanf("%d", &F[i]);
  for (int i = (1); i < (n); ++i) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    edges[a].push_back(pair<int, int>(b, c));
    edges[b].push_back(pair<int, int>(a, c));
  }
  dfs(1);
  init(1);
  for (int i = (0); i < (q); ++i) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    A[i] = a;
    B[i] = b;
    queries.push_back(pair<int, int>(c, i));
  }
  sort((mods).begin(), (mods).end(), greater<pair<int, int> >());
  sort((queries).begin(), (queries).end(), greater<pair<int, int> >());
  q = 0;
  int m = 0;
  while (q < ((int)(queries).size())) {
    while (m < ((int)(mods).size()) && mods[m].first >= queries[q].first) {
      int u = mods[m].second;
      HLD[I[u]].lit(J[u]);
      ++m;
    }
    int u = B[queries[q].second];
    int v = A[queries[q].second];
    path tu, tv;
    while (I[u] != I[v]) {
      if (depth[R[I[u]]] > depth[R[I[v]]]) {
        tu = merge(HLD[I[u]].get(0, J[u]), tu);
        u = parent[R[I[u]]].first;
      } else {
        tv = merge(HLD[I[v]].get(0, J[v]), tv);
        v = parent[R[I[v]]].first;
      }
    }
    if (J[u] < J[v]) {
      tu = merge(reverse(tu), HLD[I[u]].get(J[u] + 1, J[v]));
      tu = merge(tu, tv);
    } else {
      tv = merge(reverse(tv), HLD[I[u]].get(J[v] + 1, J[u]));
      tu = merge(tv, tu);
    }
    res[queries[q].second] = eval(tu);
    ++q;
  }
  for (int i = (0); i < (q); ++i) printf("%d\n", res[i]);
  return 0;
}

```