#include <bits/stdc++.h>
using namespace std;
template <class C>
void mini(C& a4, C b4) {
  a4 = min(a4, b4);
}
template <class C>
void maxi(C& a4, C b4) {
  a4 = max(a4, b4);
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> pair) {
  return out << "(" << pair.first << ", " << pair.second << ")";
}
template <class A, class B, class C>
struct Triple {
  A first;
  B second;
  C third;
};
template <class T>
void ResizeVec(T&, vector<long long>) {}
template <class T>
void ResizeVec(vector<T>& vec, vector<long long> sz) {
  vec.resize(sz[0]);
  sz.erase(sz.begin());
  if (sz.empty()) {
    return;
  }
  for (T& v : vec) {
    ResizeVec(v, sz);
  }
}
template <class A, class B, class C>
ostream& operator<<(ostream& out, Triple<A, B, C> t) {
  return out << "(" << t.first << ", " << t.second << ", " << t.third << ")";
}
const long long N = 2e5 + 5;
long long f[N];
struct Node {
  long long left_len, mid_val, right_len, whole;
};
Node Merge(Node a, Node b) {
  if (a.whole && b.whole) {
    return {a.left_len + b.left_len, 0, 0, 1};
  }
  if (a.whole) {
    return {a.left_len + b.left_len, b.mid_val, b.right_len, 0};
  }
  if (b.whole) {
    return {a.left_len, a.mid_val, a.right_len + b.left_len, 0};
  }
  return {a.left_len, a.mid_val + b.mid_val + f[a.right_len + b.left_len],
          b.right_len, 0};
}
struct HLD {
  struct Tree {
    Tree(long long nn) {
      M = 1;
      while (M <= nn) {
        M *= 2;
      }
      node.resize(2 * M + 5);
      ;
    }
    Node ReadNode(long long a, long long b) {
      a += M;
      b += M;
      if (a == b) {
        if (0) cout << "a=b=" << a << "\n";
        return node[a];
      }
      Node ____left = node[a];
      Node right = node[b];
      while (a / 2 != b / 2) {
        if (a % 2 == 0) {
          ____left = Merge(____left, node[a + 1]);
        }
        if (b % 2 == 1) {
          right = Merge(node[b - 1], right);
        }
        a /= 2;
        b /= 2;
      }
      return Merge(____left, right);
    }
    void Upd(long long a) {
      a += M;
      ;
      node[a] = {1, 0, 0, 1};
      a /= 2;
      while (a) {
        node[a] = Merge(node[2 * a], node[2 * a + 1]);
        a /= 2;
      }
    }
    long long M;
    vector<Node> node;
  };

 public:
  HLD(vector<vector<long long>>& slo_, long long n_, long long on_vertices_,
      long long root_ = 1) {
    n = n_;
    on_vertices = on_vertices_;
    assert(((long long)(slo_).size()) >= n_);
    slo = slo_;
    path.resize(n + 5);
    wh_path.resize(n + 5);
    ord.resize(n + 5);
    sz.resize(n + 5);
    pre.resize(n + 5);
    par.resize(n + 5);
    path_pot.resize(n + 5);
    root = root_;
    path_cnt = 0;
    d = 0;
    Dfs1(root);
    tree.push_back(Tree(1));
    for (long long p = 1; p <= path_cnt; p++) {
      tree.push_back(Tree(((long long)(path[p]).size())));
    }
  }
  bool IsAnc(long long v, long long u) {
    return pre[v] <= pre[u] && pre[u] <= pre[v] + sz[v] - 1;
  }
  long long n, path_cnt, d, root, on_vertices;
  vector<vector<long long>> slo, path;
  vector<Tree> tree;
  vector<long long> wh_path, ord, sz, pre, par, path_pot;
  void Dfs1(long long v) {
    sz[v] = 1;
    d++;
    pre[v] = d;
    long long largest_son = 0;
    for (long long vv = 0; vv < ((long long)(slo[v]).size()); vv++) {
      long long nei = slo[v][vv];
      if (pre[nei]) {
        continue;
      }
      par[nei] = v;
      Dfs1(nei);
      sz[v] += sz[nei];
      if (sz[nei] > sz[largest_son]) {
        largest_son = nei;
      }
    }
    if (largest_son == 0) {
      path_cnt++;
      path[path_cnt].push_back(v);
      wh_path[v] = path_cnt;
    } else {
      wh_path[v] = wh_path[largest_son];
      ord[v] = ord[largest_son] + 1;
      path[wh_path[v]].push_back(v);
    }
  }
  pair<vector<Triple<long long, long long, long long>>,
       vector<Triple<long long, long long, long long>>>
  GetPath(long long a, long long b) {
    vector<Triple<long long, long long, long long>> res[2];
    for (long long tr = 0; tr < 2; tr++) {
      while (1) {
        long long p = wh_path[a];
        long long mi = ord[a];
        long long ma = ((long long)(path[p]).size()) - 1;
        if (IsAnc(path[p].back(), b)) {
          long long kl = mi;
          long long kp = ma;
          while (kl <= kp) {
            long long aktc = (kl + kp) / 2;
            if (IsAnc(path[p][aktc], b)) {
              kp = aktc - 1;
              ma = aktc;
            } else {
              kl = aktc + 1;
            }
          }
        }
        res[tr].push_back({p, mi, ma});
        if (IsAnc(path[p].back(), b)) {
          break;
        }
        a = par[path[p].back()];
      }
      if (tr == 1 || !on_vertices) {
        if (res[tr].back().second == res[tr].back().third) {
          res[tr].pop_back();
        } else {
          res[tr].back().third--;
        }
      }
      swap(a, b);
    }
    return {res[0], res[1]};
  }
  void Upd(long long a, long long b) {
    auto sub = GetPath(a, b);
    vector<Triple<long long, long long, long long>> subpaths;
    if (sub.first.empty()) {
      subpaths = sub.second;
    } else {
      subpaths = sub.first;
    }
    for (auto tr : subpaths) {
      tree[tr.first].Upd(tr.second);
    }
  }
  long long Query(long long a, long long b) {
    auto subpaths = GetPath(a, b);
    vector<Triple<long long, long long, long long>> p[2] = {subpaths.first,
                                                            subpaths.second};
    ;
    ;
    Node no[2] = {{0, 0, 0, 1}, {0, 0, 0, 1}};
    for (long long wh = 0; wh < (2); ++wh) {
      for (auto tr : p[wh]) {
        no[wh] = Merge(no[wh], tree[tr.first].ReadNode(tr.second, tr.third));
      }
    }
    if (!no[1].whole) {
      swap(no[1].left_len, no[1].right_len);
    }
    for (long long tr = 0; tr < (2); ++tr) {
      ;
    }
    Node R = Merge(no[0], no[1]);
    ;
    return R.mid_val + f[R.left_len] + f[R.right_len];
  }
};
vector<vector<long long>> slo;
struct Q {
  long long cost, a, b, type;
  bool operator<(const Q& q) const {
    if (cost != q.cost) {
      return cost > q.cost;
    }
    return type < q.type;
  }
};
long long ans[N];
int main() {
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(10);
  double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  long long n, q;
  cin >> n >> q;
  ;
  slo.resize(n + 5);
  vector<Q> qs;
  for (long long i = (1); i <= (n - 1); ++i) {
    cin >> f[i];
  }
  for (long long i = (1); i <= (n - 1); ++i) {
    long long a, b, c;
    cin >> a >> b >> c;
    ;
    slo[a].push_back(b);
    slo[b].push_back(a);
    qs.push_back({c, a, b, 0});
  }
  HLD hld(slo, n, 0);
  for (long long i = (1); i <= (q); ++i) {
    long long a, b, c;
    cin >> a >> b >> c;
    ;
    qs.push_back({c, a, b, i});
  }
  sort((qs).begin(), (qs).end());
  for (auto qq : qs) {
    if (qq.type == 0) {
      ;
      hld.Upd(qq.a, qq.b);
    } else {
      ;
      ans[qq.type] = hld.Query(qq.a, qq.b);
    }
  }
  for (long long i = (1); 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;
template <class C>
void mini(C& a4, C b4) {
  a4 = min(a4, b4);
}
template <class C>
void maxi(C& a4, C b4) {
  a4 = max(a4, b4);
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> pair) {
  return out << "(" << pair.first << ", " << pair.second << ")";
}
template <class A, class B, class C>
struct Triple {
  A first;
  B second;
  C third;
};
template <class T>
void ResizeVec(T&, vector<long long>) {}
template <class T>
void ResizeVec(vector<T>& vec, vector<long long> sz) {
  vec.resize(sz[0]);
  sz.erase(sz.begin());
  if (sz.empty()) {
    return;
  }
  for (T& v : vec) {
    ResizeVec(v, sz);
  }
}
template <class A, class B, class C>
ostream& operator<<(ostream& out, Triple<A, B, C> t) {
  return out << "(" << t.first << ", " << t.second << ", " << t.third << ")";
}
const long long N = 2e5 + 5;
long long f[N];
struct Node {
  long long left_len, mid_val, right_len, whole;
};
Node Merge(Node a, Node b) {
  if (a.whole && b.whole) {
    return {a.left_len + b.left_len, 0, 0, 1};
  }
  if (a.whole) {
    return {a.left_len + b.left_len, b.mid_val, b.right_len, 0};
  }
  if (b.whole) {
    return {a.left_len, a.mid_val, a.right_len + b.left_len, 0};
  }
  return {a.left_len, a.mid_val + b.mid_val + f[a.right_len + b.left_len],
          b.right_len, 0};
}
struct HLD {
  struct Tree {
    Tree(long long nn) {
      M = 1;
      while (M <= nn) {
        M *= 2;
      }
      node.resize(2 * M + 5);
      ;
    }
    Node ReadNode(long long a, long long b) {
      a += M;
      b += M;
      if (a == b) {
        if (0) cout << "a=b=" << a << "\n";
        return node[a];
      }
      Node ____left = node[a];
      Node right = node[b];
      while (a / 2 != b / 2) {
        if (a % 2 == 0) {
          ____left = Merge(____left, node[a + 1]);
        }
        if (b % 2 == 1) {
          right = Merge(node[b - 1], right);
        }
        a /= 2;
        b /= 2;
      }
      return Merge(____left, right);
    }
    void Upd(long long a) {
      a += M;
      ;
      node[a] = {1, 0, 0, 1};
      a /= 2;
      while (a) {
        node[a] = Merge(node[2 * a], node[2 * a + 1]);
        a /= 2;
      }
    }
    long long M;
    vector<Node> node;
  };

 public:
  HLD(vector<vector<long long>>& slo_, long long n_, long long on_vertices_,
      long long root_ = 1) {
    n = n_;
    on_vertices = on_vertices_;
    assert(((long long)(slo_).size()) >= n_);
    slo = slo_;
    path.resize(n + 5);
    wh_path.resize(n + 5);
    ord.resize(n + 5);
    sz.resize(n + 5);
    pre.resize(n + 5);
    par.resize(n + 5);
    path_pot.resize(n + 5);
    root = root_;
    path_cnt = 0;
    d = 0;
    Dfs1(root);
    tree.push_back(Tree(1));
    for (long long p = 1; p <= path_cnt; p++) {
      tree.push_back(Tree(((long long)(path[p]).size())));
    }
  }
  bool IsAnc(long long v, long long u) {
    return pre[v] <= pre[u] && pre[u] <= pre[v] + sz[v] - 1;
  }
  long long n, path_cnt, d, root, on_vertices;
  vector<vector<long long>> slo, path;
  vector<Tree> tree;
  vector<long long> wh_path, ord, sz, pre, par, path_pot;
  void Dfs1(long long v) {
    sz[v] = 1;
    d++;
    pre[v] = d;
    long long largest_son = 0;
    for (long long vv = 0; vv < ((long long)(slo[v]).size()); vv++) {
      long long nei = slo[v][vv];
      if (pre[nei]) {
        continue;
      }
      par[nei] = v;
      Dfs1(nei);
      sz[v] += sz[nei];
      if (sz[nei] > sz[largest_son]) {
        largest_son = nei;
      }
    }
    if (largest_son == 0) {
      path_cnt++;
      path[path_cnt].push_back(v);
      wh_path[v] = path_cnt;
    } else {
      wh_path[v] = wh_path[largest_son];
      ord[v] = ord[largest_son] + 1;
      path[wh_path[v]].push_back(v);
    }
  }
  pair<vector<Triple<long long, long long, long long>>,
       vector<Triple<long long, long long, long long>>>
  GetPath(long long a, long long b) {
    vector<Triple<long long, long long, long long>> res[2];
    for (long long tr = 0; tr < 2; tr++) {
      while (1) {
        long long p = wh_path[a];
        long long mi = ord[a];
        long long ma = ((long long)(path[p]).size()) - 1;
        if (IsAnc(path[p].back(), b)) {
          long long kl = mi;
          long long kp = ma;
          while (kl <= kp) {
            long long aktc = (kl + kp) / 2;
            if (IsAnc(path[p][aktc], b)) {
              kp = aktc - 1;
              ma = aktc;
            } else {
              kl = aktc + 1;
            }
          }
        }
        res[tr].push_back({p, mi, ma});
        if (IsAnc(path[p].back(), b)) {
          break;
        }
        a = par[path[p].back()];
      }
      if (tr == 1 || !on_vertices) {
        if (res[tr].back().second == res[tr].back().third) {
          res[tr].pop_back();
        } else {
          res[tr].back().third--;
        }
      }
      swap(a, b);
    }
    return {res[0], res[1]};
  }
  void Upd(long long a, long long b) {
    auto sub = GetPath(a, b);
    vector<Triple<long long, long long, long long>> subpaths;
    if (sub.first.empty()) {
      subpaths = sub.second;
    } else {
      subpaths = sub.first;
    }
    for (auto tr : subpaths) {
      tree[tr.first].Upd(tr.second);
    }
  }
  long long Query(long long a, long long b) {
    auto subpaths = GetPath(a, b);
    vector<Triple<long long, long long, long long>> p[2] = {subpaths.first,
                                                            subpaths.second};
    ;
    ;
    Node no[2] = {{0, 0, 0, 1}, {0, 0, 0, 1}};
    for (long long wh = 0; wh < (2); ++wh) {
      for (auto tr : p[wh]) {
        no[wh] = Merge(no[wh], tree[tr.first].ReadNode(tr.second, tr.third));
      }
    }
    if (!no[1].whole) {
      swap(no[1].left_len, no[1].right_len);
    }
    for (long long tr = 0; tr < (2); ++tr) {
      ;
    }
    Node R = Merge(no[0], no[1]);
    ;
    return R.mid_val + f[R.left_len] + f[R.right_len];
  }
};
vector<vector<long long>> slo;
struct Q {
  long long cost, a, b, type;
  bool operator<(const Q& q) const {
    if (cost != q.cost) {
      return cost > q.cost;
    }
    return type < q.type;
  }
};
long long ans[N];
int main() {
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(10);
  double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  long long n, q;
  cin >> n >> q;
  ;
  slo.resize(n + 5);
  vector<Q> qs;
  for (long long i = (1); i <= (n - 1); ++i) {
    cin >> f[i];
  }
  for (long long i = (1); i <= (n - 1); ++i) {
    long long a, b, c;
    cin >> a >> b >> c;
    ;
    slo[a].push_back(b);
    slo[b].push_back(a);
    qs.push_back({c, a, b, 0});
  }
  HLD hld(slo, n, 0);
  for (long long i = (1); i <= (q); ++i) {
    long long a, b, c;
    cin >> a >> b >> c;
    ;
    qs.push_back({c, a, b, i});
  }
  sort((qs).begin(), (qs).end());
  for (auto qq : qs) {
    if (qq.type == 0) {
      ;
      hld.Upd(qq.a, qq.b);
    } else {
      ;
      ans[qq.type] = hld.Query(qq.a, qq.b);
    }
  }
  for (long long i = (1); i <= (q); ++i) {
    cout << ans[i] << "\n";
  }
  return 0;
}

```