#include <bits/stdc++.h>
using namespace std;
const int N = 101000;
struct quer {
  int n1, n2, val, poz;
};
quer qu[N];
int n, q, f[N];
int rez[N];
vector<pair<int, int> > v[N];
int we[N], path[N], pozPath[N], lastNod[N], pathCur, valP[N], p[N], sizePath[N],
    niv[N];
void calcwe(int nod, int p) {
  we[nod] = 1;
  for (vector<pair<int, int> >::iterator it = v[nod].begin();
       it != v[nod].end(); ++it)
    if (it->first != p) {
      valP[it->first] = it->second;
      niv[it->first] = niv[nod] + 1;
      calcwe(it->first, nod);
      we[nod] += we[it->first];
    }
}
void calc(int nod, int pozc, int p) {
  path[nod] = pathCur;
  sizePath[pathCur]++;
  pozPath[nod] = pozc;
  vector<pair<int, int> >::iterator it;
  int smax = 0, elmax;
  for (it = v[nod].begin(); it != v[nod].end(); ++it)
    if (it->first != p)
      if (we[it->first] > smax) {
        smax = we[it->first];
        elmax = it->first;
      }
  if (!smax) return;
  calc(elmax, pozc + 1, nod);
  for (it = v[nod].begin(); it != v[nod].end(); ++it)
    if (it->first != p && it->first != elmax) {
      ++pathCur;
      lastNod[pathCur] = nod;
      calc(it->first, 1, nod);
    }
}
vector<int> aint[N], last[N], first[N];
void buildhp() {
  niv[1] = 1;
  calcwe(1, -1);
  pathCur = 1;
  calc(1, 1, -1);
  for (int i = 1; i <= pathCur; ++i) {
    aint[i].resize(4 * sizePath[i]);
    first[i].resize(4 * sizePath[i]);
    last[i].resize(4 * sizePath[i]);
  }
}
bool cmp(quer a, quer b) { return a.val > b.val; }
bool cmp2(int a, int b) { return valP[a] < valP[b]; }
void update(int nr, int nod, int pozx, int pozy, int poz) {
  if (pozx == pozy) {
    aint[nr][nod] = f[1];
    first[nr][nod] = 1;
    last[nr][nod] = 1;
    return;
  }
  int mid = (pozx + pozy) / 2;
  if (mid >= poz)
    update(nr, 2 * nod, pozx, mid, poz);
  else
    update(nr, 2 * nod + 1, mid + 1, pozy, poz);
  first[nr][nod] = first[nr][2 * nod];
  if (first[nr][2 * nod] == mid - pozx + 1)
    first[nr][nod] += first[nr][2 * nod + 1];
  last[nr][nod] = last[nr][2 * nod + 1];
  if (last[nr][2 * nod + 1] == pozy - mid) last[nr][nod] += last[nr][2 * nod];
  aint[nr][nod] = aint[nr][2 * nod] + aint[nr][2 * nod + 1] -
                  f[last[nr][2 * nod]] - f[first[nr][2 * nod + 1]] +
                  f[last[nr][2 * nod] + first[nr][2 * nod + 1]];
}
int re, las1, las2;
void query(int nr, int nod, int pozx, int pozy, int poz1, int poz2, int &las) {
  if (pozx >= poz1 && poz2 >= pozy) {
    re =
        re - f[las] - f[last[nr][nod]] + f[las + last[nr][nod]] + aint[nr][nod];
    if (first[nr][nod] == pozy - pozx + 1)
      las += first[nr][nod];
    else
      las = first[nr][nod];
    return;
  }
  int mid = (pozx + pozy) / 2;
  if (mid < poz2) query(nr, 2 * nod + 1, mid + 1, pozy, poz1, poz2, las);
  if (mid >= poz1) query(nr, 2 * nod, pozx, mid, poz1, poz2, las);
}
int solveq(int nod1, int nod2) {
  re = las1 = las2 = 0;
  while (path[nod1] != path[nod2]) {
    int pa1 = path[nod1], pa2 = path[nod2];
    if (niv[lastNod[pa1]] > niv[lastNod[pa2]]) {
      query(pa1, 1, 1, sizePath[pa1], 1, pozPath[nod1], las1);
      nod1 = lastNod[pa1];
    } else {
      query(pa2, 1, 1, sizePath[pa2], 1, pozPath[nod2], las2);
      nod2 = lastNod[pa2];
    }
  }
  int pa = path[nod1];
  if (nod1 == nod2) return re - f[las1] - f[las2] + f[las1 + las2];
  if (niv[nod1] < niv[nod2]) {
    query(pa, 1, 1, sizePath[pa], pozPath[nod1] + 1, pozPath[nod2], las2);
  } else {
    query(pa, 1, 1, sizePath[pa], pozPath[nod2] + 1, pozPath[nod1], las1);
  }
  re = re - f[las1] - f[las2] + f[las1 + las2];
  return re;
}
void calcrez() {
  int i, j = n;
  sort(qu + 1, qu + q + 1, cmp);
  for (i = 2; i <= n; ++i) p[i] = i;
  sort(p + 2, p + n + 1, cmp2);
  for (i = 1; i <= q; ++i) {
    while (j > 1 && valP[p[j]] >= qu[i].val) {
      update(path[p[j]], 1, 1, sizePath[path[p[j]]], pozPath[p[j]]);
      --j;
    }
    rez[qu[i].poz] = solveq(qu[i].n1, qu[i].n2);
  }
}
int main() {
  int i;
  cin >> n >> q;
  for (i = 1; i < n; ++i) cin >> f[i];
  for (i = 1; i < n; ++i) {
    int a, b, val;
    cin >> a >> b >> val;
    v[a].push_back(pair<int, int>(b, val));
    v[b].push_back(pair<int, int>(a, val));
  }
  buildhp();
  for (i = 1; i <= q; ++i) {
    cin >> qu[i].n1 >> qu[i].n2 >> qu[i].val;
    qu[i].poz = i;
  }
  calcrez();
  for (i = 1; i <= q; ++i) cout << rez[i] << "\n";
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
const int N = 101000;
struct quer {
  int n1, n2, val, poz;
};
quer qu[N];
int n, q, f[N];
int rez[N];
vector<pair<int, int> > v[N];
int we[N], path[N], pozPath[N], lastNod[N], pathCur, valP[N], p[N], sizePath[N],
    niv[N];
void calcwe(int nod, int p) {
  we[nod] = 1;
  for (vector<pair<int, int> >::iterator it = v[nod].begin();
       it != v[nod].end(); ++it)
    if (it->first != p) {
      valP[it->first] = it->second;
      niv[it->first] = niv[nod] + 1;
      calcwe(it->first, nod);
      we[nod] += we[it->first];
    }
}
void calc(int nod, int pozc, int p) {
  path[nod] = pathCur;
  sizePath[pathCur]++;
  pozPath[nod] = pozc;
  vector<pair<int, int> >::iterator it;
  int smax = 0, elmax;
  for (it = v[nod].begin(); it != v[nod].end(); ++it)
    if (it->first != p)
      if (we[it->first] > smax) {
        smax = we[it->first];
        elmax = it->first;
      }
  if (!smax) return;
  calc(elmax, pozc + 1, nod);
  for (it = v[nod].begin(); it != v[nod].end(); ++it)
    if (it->first != p && it->first != elmax) {
      ++pathCur;
      lastNod[pathCur] = nod;
      calc(it->first, 1, nod);
    }
}
vector<int> aint[N], last[N], first[N];
void buildhp() {
  niv[1] = 1;
  calcwe(1, -1);
  pathCur = 1;
  calc(1, 1, -1);
  for (int i = 1; i <= pathCur; ++i) {
    aint[i].resize(4 * sizePath[i]);
    first[i].resize(4 * sizePath[i]);
    last[i].resize(4 * sizePath[i]);
  }
}
bool cmp(quer a, quer b) { return a.val > b.val; }
bool cmp2(int a, int b) { return valP[a] < valP[b]; }
void update(int nr, int nod, int pozx, int pozy, int poz) {
  if (pozx == pozy) {
    aint[nr][nod] = f[1];
    first[nr][nod] = 1;
    last[nr][nod] = 1;
    return;
  }
  int mid = (pozx + pozy) / 2;
  if (mid >= poz)
    update(nr, 2 * nod, pozx, mid, poz);
  else
    update(nr, 2 * nod + 1, mid + 1, pozy, poz);
  first[nr][nod] = first[nr][2 * nod];
  if (first[nr][2 * nod] == mid - pozx + 1)
    first[nr][nod] += first[nr][2 * nod + 1];
  last[nr][nod] = last[nr][2 * nod + 1];
  if (last[nr][2 * nod + 1] == pozy - mid) last[nr][nod] += last[nr][2 * nod];
  aint[nr][nod] = aint[nr][2 * nod] + aint[nr][2 * nod + 1] -
                  f[last[nr][2 * nod]] - f[first[nr][2 * nod + 1]] +
                  f[last[nr][2 * nod] + first[nr][2 * nod + 1]];
}
int re, las1, las2;
void query(int nr, int nod, int pozx, int pozy, int poz1, int poz2, int &las) {
  if (pozx >= poz1 && poz2 >= pozy) {
    re =
        re - f[las] - f[last[nr][nod]] + f[las + last[nr][nod]] + aint[nr][nod];
    if (first[nr][nod] == pozy - pozx + 1)
      las += first[nr][nod];
    else
      las = first[nr][nod];
    return;
  }
  int mid = (pozx + pozy) / 2;
  if (mid < poz2) query(nr, 2 * nod + 1, mid + 1, pozy, poz1, poz2, las);
  if (mid >= poz1) query(nr, 2 * nod, pozx, mid, poz1, poz2, las);
}
int solveq(int nod1, int nod2) {
  re = las1 = las2 = 0;
  while (path[nod1] != path[nod2]) {
    int pa1 = path[nod1], pa2 = path[nod2];
    if (niv[lastNod[pa1]] > niv[lastNod[pa2]]) {
      query(pa1, 1, 1, sizePath[pa1], 1, pozPath[nod1], las1);
      nod1 = lastNod[pa1];
    } else {
      query(pa2, 1, 1, sizePath[pa2], 1, pozPath[nod2], las2);
      nod2 = lastNod[pa2];
    }
  }
  int pa = path[nod1];
  if (nod1 == nod2) return re - f[las1] - f[las2] + f[las1 + las2];
  if (niv[nod1] < niv[nod2]) {
    query(pa, 1, 1, sizePath[pa], pozPath[nod1] + 1, pozPath[nod2], las2);
  } else {
    query(pa, 1, 1, sizePath[pa], pozPath[nod2] + 1, pozPath[nod1], las1);
  }
  re = re - f[las1] - f[las2] + f[las1 + las2];
  return re;
}
void calcrez() {
  int i, j = n;
  sort(qu + 1, qu + q + 1, cmp);
  for (i = 2; i <= n; ++i) p[i] = i;
  sort(p + 2, p + n + 1, cmp2);
  for (i = 1; i <= q; ++i) {
    while (j > 1 && valP[p[j]] >= qu[i].val) {
      update(path[p[j]], 1, 1, sizePath[path[p[j]]], pozPath[p[j]]);
      --j;
    }
    rez[qu[i].poz] = solveq(qu[i].n1, qu[i].n2);
  }
}
int main() {
  int i;
  cin >> n >> q;
  for (i = 1; i < n; ++i) cin >> f[i];
  for (i = 1; i < n; ++i) {
    int a, b, val;
    cin >> a >> b >> val;
    v[a].push_back(pair<int, int>(b, val));
    v[b].push_back(pair<int, int>(a, val));
  }
  buildhp();
  for (i = 1; i <= q; ++i) {
    cin >> qu[i].n1 >> qu[i].n2 >> qu[i].val;
    qu[i].poz = i;
  }
  calcrez();
  for (i = 1; i <= q; ++i) cout << rez[i] << "\n";
  return 0;
}

```