#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream& operator<<(ostream& o, const pair<T, U>& v) {
  return o << "(" << v.first << ", " << v.second << ")";
}
template <class T>
ostream& operator<<(ostream& o, const vector<T>& v) {
  o << "{";
  for (int i = 0; i < (int)((int)((v).size())); ++i)
    o << (i ? ", " : "") << v[i];
  return o << "}";
}
template <class T, class U>
ostream& operator<<(ostream& o, const map<T, U>& v) {
  o << "{";
  for (const auto& e : v) o << e << ", ";
  return o << "}";
}
template <class T>
string to_s(const T& v) {
  ostringstream is;
  is << v;
  return is.str();
}
const int dx[] = {0, -1, 0, 1};
const int dy[] = {-1, 0, 1, 0};
const int MAX_N = 3e5 + 10;
int f[MAX_N];
vector<int> G[MAX_N];
int start[MAX_N];
int end[MAX_N];
pair<int, int> upsegpos[MAX_N];
pair<int, int> downsegpos[MAX_N];
string treech;
bool debug;
inline pair<int, pair<int, int> > merge(pair<int, pair<int, int> > sle,
                                        pair<int, pair<int, int> > sri,
                                        int llen, int rlen) {
  llen = max(0, llen);
  rlen = max(0, rlen);
  int rsum = sle.second.first + sri.second.first;
  if (sle.second.second != llen && sri.first != rlen) {
    if (sle.second.second + sri.first > 1)
      rsum += f[(sle.second.second + sri.first) / 2 - 1];
  } else {
    if (sle.second.second == llen) sle.first += sri.first;
    if (sri.first == rlen) sri.second.second += sle.second.second;
  }
  auto ret = make_pair(sle.first, make_pair(rsum, sri.second.second));
  ;
  return ret;
}
struct SqrtLogSeg {
  vector<int> seg;
  vector<long long> le;
  vector<long long> ri;
  vector<long long> sum;
  void init() {
    int n = seg.size();
    sum.resize(n * 4);
    le.resize(n * 4);
    ri.resize(n * 4);
  }
  inline pair<int, pair<int, int> > query(int cl, int cr, int l, int r, int k) {
    if (cr <= l || r <= cl) {
      return make_pair(0, make_pair(0, 0));
    }
    if (l <= cl && cr <= r) {
      return make_pair(le[k], make_pair(sum[k], ri[k]));
    }
    int mid = (cl + cr) / 2;
    auto sle = query(cl, mid, l, r, k * 2 + 1);
    auto sri = query(mid, cr, l, r, k * 2 + 2);
    return merge(sle, sri, mid - max(l, cl), min(cr, r) - mid);
  }
  pair<int, pair<int, int> > query(int l, int r) {
    return query(0, (int)((seg).size()), l, r, 0);
  }
  pair<int, pair<int, int> > update(int cl, int cr, int q, int k) {
    if (cr <= q || q < cl) {
    } else if (cl == q && q + 1 == cr) {
      sum[k] = 0;
      le[k] = 1;
      ri[k] = 1;
    } else {
      int mid = (cl + cr) / 2;
      auto sle = update(cl, mid, q, k * 2 + 1);
      auto sri = update(mid, cr, q, k * 2 + 2);
      auto ret = merge(sle, sri, mid - cl, cr - mid);
      le[k] = ret.first;
      sum[k] = ret.second.first;
      ri[k] = ret.second.second;
    }
    return make_pair(le[k], make_pair(sum[k], ri[k]));
  }
  pair<int, pair<int, int> > update(int a) {
    return update(0, (int)((seg).size()), a, 0);
  }
};
SqrtLogSeg segs[MAX_N * 3];
int segscnt;
int subwe[MAX_N];
int depth[MAX_N];
int subtdfs(int cv, int p, int d) {
  subwe[cv] = 1;
  depth[cv] = d;
  for (auto e : G[cv])
    if (e != p) subwe[cv] += subtdfs(e, cv, d + 1);
  return subwe[cv];
}
int pnodeseg[MAX_N];
void makeheavy(int cv, int p) {
  vector<int> seg;
  int segp = p;
  while (true) {
    auto ne = make_pair(make_pair(-1, 0), 0);
    for (auto e : G[cv])
      if (e != p) ne = max(make_pair(make_pair(subwe[e], e), e), ne);
    pnodeseg[cv] = segp;
    seg.push_back(cv);
    if (ne.first.first == -1) break;
    int np = cv;
    int ncv = ne.first.second;
    for (auto e : G[cv]) {
      if (e == p) continue;
      if (e != ne.first.second) makeheavy(e, cv);
    }
    p = np;
    cv = ncv;
  }
  for (int i = 0; i < (int)((seg).size()); ++i)
    downsegpos[seg[i]] = make_pair(segscnt, i);
  segs[segscnt++].seg = seg;
  segs[segscnt - 1].init();
  reverse((seg).begin(), (seg).end());
  for (int i = 0; i < (int)((seg).size()); ++i)
    upsegpos[seg[i]] = make_pair(segscnt, i);
  segs[segscnt++].seg = seg;
  segs[segscnt - 1].init();
}
inline vector<pair<int, pair<int, int> > > getseg(int s, int t) {
  if (s == t) {
    vector<pair<int, pair<int, int> > > ret;
    ret.push_back(make_pair(upsegpos[s].first,
                            make_pair(upsegpos[s].second, upsegpos[s].second)));
    ret.push_back(
        make_pair(downsegpos[s].first,
                  make_pair(downsegpos[s].second, downsegpos[s].second)));
    return ret;
  }
  static vector<pair<int, pair<int, int> > > sret, tret;
  sret.clear();
  tret.clear();
  int ss = s;
  int tt = t;
  while (s != t) {
    int ps = segs[upsegpos[s].first].seg.back();
    int pt = segs[downsegpos[t].first].seg[0];
    if (ps == pt) {
      if (depth[s] < depth[t]) {
        tret.push_back(
            make_pair(downsegpos[t].first,
                      make_pair(downsegpos[s].second, downsegpos[t].second)));
      } else {
        sret.push_back(
            make_pair(upsegpos[s].first,
                      make_pair(upsegpos[s].second, upsegpos[t].second)));
      }
      break;
    }
    if (depth[ps] < depth[pt]) {
      tret.push_back(
          make_pair(downsegpos[t].first, make_pair(0, downsegpos[t].second)));
      t = pnodeseg[t];
    } else {
      sret.push_back(
          make_pair(upsegpos[s].first,
                    make_pair(upsegpos[s].second,
                              segs[upsegpos[s].first].seg.size() - 1)));
      s = pnodeseg[s];
    }
    if (s == t) {
      if (ss < tt)
        sret.push_back(
            make_pair(downsegpos[t].first,
                      make_pair(downsegpos[t].second, downsegpos[t].second)));
      else
        sret.push_back(
            make_pair(upsegpos[t].first,
                      make_pair(upsegpos[t].second, upsegpos[t].second)));
    }
  }
  for (int i = (int)((tret).size()) - 1; i >= 0; --i) sret.push_back(tret[i]);
  return sret;
}
int main(int argc, char* argv[]) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < (int)(n - 1); ++i) cin >> f[i];
  vector<pair<pair<int, int>, pair<int, int> > > ed;
  for (int i = 0; i < (int)(n - 1); ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    G[a].push_back(i + n);
    G[i + n].push_back(a);
    G[i + n].push_back(b);
    G[b].push_back(i + n);
    ed.push_back(make_pair(make_pair(-c, i + n), make_pair(a, b)));
  }
  sort((ed).begin(), (ed).end());
  subtdfs(0, -1, 0);
  makeheavy(0, -1);
  for (int i = 0; i < (int)(n); ++i) {
    auto seg = getseg(i, i);
    for (auto e : seg) segs[e.first].update(e.second.first);
  }
  vector<pair<pair<int, int>, pair<int, int> > > query;
  vector<int> ans(q);
  for (int i = 0; i < (int)(q); ++i) {
    int u, v, l;
    cin >> u >> v >> l;
    --u, --v;
    query.push_back(make_pair(make_pair(-l, i), make_pair(u, v)));
  }
  sort((query).begin(), (query).end());
  int eidx = 0;
  for (auto e : query) {
    while (eidx < (int)((ed).size()) && ed[eidx].first.first <= e.first.first) {
      int p = ed[eidx].first.second;
      for (auto e : getseg(p, p)) {
        segs[e.first].update(e.second.first);
      }
      ++eidx;
    }
    pair<int, pair<int, int> > cur(0, make_pair(0, 0));
    int len = 0;
    for (auto se : getseg(e.second.first, e.second.second)) {
      auto p = segs[se.first].query(se.second.first, se.second.second + 1);
      cur = merge(cur, p, len, se.second.second + 1 - se.second.first);
      len += se.second.second - se.second.first + 1;
    }
    if (cur.first > 1) cur.second.first += f[cur.first / 2 - 1];
    if (cur.second.second > 1 && cur.second.second != len)
      cur.second.first += f[cur.second.second / 2 - 1];
    ans[e.first.second] = cur.second.first;
  }
  for (auto e : ans) cout << e << '\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;
template <class T, class U>
ostream& operator<<(ostream& o, const pair<T, U>& v) {
  return o << "(" << v.first << ", " << v.second << ")";
}
template <class T>
ostream& operator<<(ostream& o, const vector<T>& v) {
  o << "{";
  for (int i = 0; i < (int)((int)((v).size())); ++i)
    o << (i ? ", " : "") << v[i];
  return o << "}";
}
template <class T, class U>
ostream& operator<<(ostream& o, const map<T, U>& v) {
  o << "{";
  for (const auto& e : v) o << e << ", ";
  return o << "}";
}
template <class T>
string to_s(const T& v) {
  ostringstream is;
  is << v;
  return is.str();
}
const int dx[] = {0, -1, 0, 1};
const int dy[] = {-1, 0, 1, 0};
const int MAX_N = 3e5 + 10;
int f[MAX_N];
vector<int> G[MAX_N];
int start[MAX_N];
int end[MAX_N];
pair<int, int> upsegpos[MAX_N];
pair<int, int> downsegpos[MAX_N];
string treech;
bool debug;
inline pair<int, pair<int, int> > merge(pair<int, pair<int, int> > sle,
                                        pair<int, pair<int, int> > sri,
                                        int llen, int rlen) {
  llen = max(0, llen);
  rlen = max(0, rlen);
  int rsum = sle.second.first + sri.second.first;
  if (sle.second.second != llen && sri.first != rlen) {
    if (sle.second.second + sri.first > 1)
      rsum += f[(sle.second.second + sri.first) / 2 - 1];
  } else {
    if (sle.second.second == llen) sle.first += sri.first;
    if (sri.first == rlen) sri.second.second += sle.second.second;
  }
  auto ret = make_pair(sle.first, make_pair(rsum, sri.second.second));
  ;
  return ret;
}
struct SqrtLogSeg {
  vector<int> seg;
  vector<long long> le;
  vector<long long> ri;
  vector<long long> sum;
  void init() {
    int n = seg.size();
    sum.resize(n * 4);
    le.resize(n * 4);
    ri.resize(n * 4);
  }
  inline pair<int, pair<int, int> > query(int cl, int cr, int l, int r, int k) {
    if (cr <= l || r <= cl) {
      return make_pair(0, make_pair(0, 0));
    }
    if (l <= cl && cr <= r) {
      return make_pair(le[k], make_pair(sum[k], ri[k]));
    }
    int mid = (cl + cr) / 2;
    auto sle = query(cl, mid, l, r, k * 2 + 1);
    auto sri = query(mid, cr, l, r, k * 2 + 2);
    return merge(sle, sri, mid - max(l, cl), min(cr, r) - mid);
  }
  pair<int, pair<int, int> > query(int l, int r) {
    return query(0, (int)((seg).size()), l, r, 0);
  }
  pair<int, pair<int, int> > update(int cl, int cr, int q, int k) {
    if (cr <= q || q < cl) {
    } else if (cl == q && q + 1 == cr) {
      sum[k] = 0;
      le[k] = 1;
      ri[k] = 1;
    } else {
      int mid = (cl + cr) / 2;
      auto sle = update(cl, mid, q, k * 2 + 1);
      auto sri = update(mid, cr, q, k * 2 + 2);
      auto ret = merge(sle, sri, mid - cl, cr - mid);
      le[k] = ret.first;
      sum[k] = ret.second.first;
      ri[k] = ret.second.second;
    }
    return make_pair(le[k], make_pair(sum[k], ri[k]));
  }
  pair<int, pair<int, int> > update(int a) {
    return update(0, (int)((seg).size()), a, 0);
  }
};
SqrtLogSeg segs[MAX_N * 3];
int segscnt;
int subwe[MAX_N];
int depth[MAX_N];
int subtdfs(int cv, int p, int d) {
  subwe[cv] = 1;
  depth[cv] = d;
  for (auto e : G[cv])
    if (e != p) subwe[cv] += subtdfs(e, cv, d + 1);
  return subwe[cv];
}
int pnodeseg[MAX_N];
void makeheavy(int cv, int p) {
  vector<int> seg;
  int segp = p;
  while (true) {
    auto ne = make_pair(make_pair(-1, 0), 0);
    for (auto e : G[cv])
      if (e != p) ne = max(make_pair(make_pair(subwe[e], e), e), ne);
    pnodeseg[cv] = segp;
    seg.push_back(cv);
    if (ne.first.first == -1) break;
    int np = cv;
    int ncv = ne.first.second;
    for (auto e : G[cv]) {
      if (e == p) continue;
      if (e != ne.first.second) makeheavy(e, cv);
    }
    p = np;
    cv = ncv;
  }
  for (int i = 0; i < (int)((seg).size()); ++i)
    downsegpos[seg[i]] = make_pair(segscnt, i);
  segs[segscnt++].seg = seg;
  segs[segscnt - 1].init();
  reverse((seg).begin(), (seg).end());
  for (int i = 0; i < (int)((seg).size()); ++i)
    upsegpos[seg[i]] = make_pair(segscnt, i);
  segs[segscnt++].seg = seg;
  segs[segscnt - 1].init();
}
inline vector<pair<int, pair<int, int> > > getseg(int s, int t) {
  if (s == t) {
    vector<pair<int, pair<int, int> > > ret;
    ret.push_back(make_pair(upsegpos[s].first,
                            make_pair(upsegpos[s].second, upsegpos[s].second)));
    ret.push_back(
        make_pair(downsegpos[s].first,
                  make_pair(downsegpos[s].second, downsegpos[s].second)));
    return ret;
  }
  static vector<pair<int, pair<int, int> > > sret, tret;
  sret.clear();
  tret.clear();
  int ss = s;
  int tt = t;
  while (s != t) {
    int ps = segs[upsegpos[s].first].seg.back();
    int pt = segs[downsegpos[t].first].seg[0];
    if (ps == pt) {
      if (depth[s] < depth[t]) {
        tret.push_back(
            make_pair(downsegpos[t].first,
                      make_pair(downsegpos[s].second, downsegpos[t].second)));
      } else {
        sret.push_back(
            make_pair(upsegpos[s].first,
                      make_pair(upsegpos[s].second, upsegpos[t].second)));
      }
      break;
    }
    if (depth[ps] < depth[pt]) {
      tret.push_back(
          make_pair(downsegpos[t].first, make_pair(0, downsegpos[t].second)));
      t = pnodeseg[t];
    } else {
      sret.push_back(
          make_pair(upsegpos[s].first,
                    make_pair(upsegpos[s].second,
                              segs[upsegpos[s].first].seg.size() - 1)));
      s = pnodeseg[s];
    }
    if (s == t) {
      if (ss < tt)
        sret.push_back(
            make_pair(downsegpos[t].first,
                      make_pair(downsegpos[t].second, downsegpos[t].second)));
      else
        sret.push_back(
            make_pair(upsegpos[t].first,
                      make_pair(upsegpos[t].second, upsegpos[t].second)));
    }
  }
  for (int i = (int)((tret).size()) - 1; i >= 0; --i) sret.push_back(tret[i]);
  return sret;
}
int main(int argc, char* argv[]) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < (int)(n - 1); ++i) cin >> f[i];
  vector<pair<pair<int, int>, pair<int, int> > > ed;
  for (int i = 0; i < (int)(n - 1); ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    G[a].push_back(i + n);
    G[i + n].push_back(a);
    G[i + n].push_back(b);
    G[b].push_back(i + n);
    ed.push_back(make_pair(make_pair(-c, i + n), make_pair(a, b)));
  }
  sort((ed).begin(), (ed).end());
  subtdfs(0, -1, 0);
  makeheavy(0, -1);
  for (int i = 0; i < (int)(n); ++i) {
    auto seg = getseg(i, i);
    for (auto e : seg) segs[e.first].update(e.second.first);
  }
  vector<pair<pair<int, int>, pair<int, int> > > query;
  vector<int> ans(q);
  for (int i = 0; i < (int)(q); ++i) {
    int u, v, l;
    cin >> u >> v >> l;
    --u, --v;
    query.push_back(make_pair(make_pair(-l, i), make_pair(u, v)));
  }
  sort((query).begin(), (query).end());
  int eidx = 0;
  for (auto e : query) {
    while (eidx < (int)((ed).size()) && ed[eidx].first.first <= e.first.first) {
      int p = ed[eidx].first.second;
      for (auto e : getseg(p, p)) {
        segs[e.first].update(e.second.first);
      }
      ++eidx;
    }
    pair<int, pair<int, int> > cur(0, make_pair(0, 0));
    int len = 0;
    for (auto se : getseg(e.second.first, e.second.second)) {
      auto p = segs[se.first].query(se.second.first, se.second.second + 1);
      cur = merge(cur, p, len, se.second.second + 1 - se.second.first);
      len += se.second.second - se.second.first + 1;
    }
    if (cur.first > 1) cur.second.first += f[cur.first / 2 - 1];
    if (cur.second.second > 1 && cur.second.second != len)
      cur.second.first += f[cur.second.second / 2 - 1];
    ans[e.first.second] = cur.second.first;
  }
  for (auto e : ans) cout << e << '\n';
  return 0;
}

```