#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010, OFF = (1 << 19) + 10;
struct struktura {
  int vrijeme, tip, a, b, indeks;
  struktura() {}
  struktura(int _vrijeme, int _tip, int _a, int _b = 0, int _indeks = 0) {
    vrijeme = _vrijeme;
    tip = _tip;
    a = _a;
    b = _b;
    indeks = _indeks;
  }
};
int cmp(struktura prva, struktura druga) {
  if (prva.vrijeme != druga.vrijeme) return prva.vrijeme > druga.vrijeme;
  if (prva.tip != druga.tip) return prva.tip < druga.tip;
  if (prva.a != druga.a) return prva.a < druga.a;
  if (prva.b != druga.b) return prva.b < druga.b;
  return prva.indeks < druga.indeks;
}
struct node {
  int velicina, x, prefix, suffix;
  node(int _velicina = 0, int _x = 0, int _prefix = 0, int _suffix = 0) {
    velicina = _velicina;
    x = _x;
    prefix = _prefix;
    suffix = _suffix;
  }
};
int f[MAXN];
node merge(node a, node b) {
  node ret;
  ret.velicina = a.velicina + b.velicina;
  ret.x = a.x + b.x;
  if (a.velicina == 0 && b.velicina == 0)
    return a;
  else if (a.velicina == 0)
    return b;
  else if (b.velicina == 0)
    return a;
  if (a.prefix == a.velicina && b.prefix == b.velicina) {
    ret.prefix = ret.suffix = ret.velicina;
  } else if (a.prefix == a.velicina) {
    ret.prefix = a.velicina + b.prefix;
    ret.suffix = b.suffix;
  } else if (b.prefix == b.velicina) {
    ret.prefix = a.prefix;
    ret.suffix = a.suffix + b.velicina;
  } else {
    ret.prefix = a.prefix;
    ret.suffix = b.suffix;
    ret.x += f[a.suffix + b.prefix];
  }
  return ret;
}
int n, q, off;
int rj[MAXN];
int cijena[MAXN], brid[MAXN];
int dubina[MAXN], tata[MAXN], podstablo[MAXN];
int moj_lanac[MAXN], glava[MAXN], pos[MAXN];
int pos_sad = -1, lanac_sad = 1;
vector<pair<int, int> > graf[MAXN];
vector<struktura> event;
node tur[OFF];
int izgradi_podstabla(int cvor, int roditelj, int d) {
  dubina[cvor] = d;
  podstablo[cvor] = 1;
  for (int i = 0; i < graf[cvor].size(); i++) {
    if (graf[cvor][i].first == roditelj) continue;
    brid[graf[cvor][i].second] = graf[cvor][i].first;
    tata[graf[cvor][i].first] = cvor;
    podstablo[cvor] += izgradi_podstabla(graf[cvor][i].first, cvor, d + 1);
  }
  return podstablo[cvor];
}
void hld(int cvor, int roditelj) {
  if (!glava[lanac_sad]) glava[lanac_sad] = cvor;
  pos[cvor] = ++pos_sad;
  moj_lanac[cvor] = lanac_sad;
  int maksi = -1, koji = -1;
  for (int i = 0; i < graf[cvor].size(); i++) {
    if (graf[cvor][i].first == roditelj) continue;
    if (podstablo[graf[cvor][i].first] > maksi) {
      maksi = podstablo[graf[cvor][i].first];
      koji = i;
    }
  }
  if (koji >= 0) hld(graf[cvor][koji].first, cvor);
  for (int i = 0; i < graf[cvor].size(); i++) {
    if (graf[cvor][i].first == roditelj) continue;
    if (koji == i) continue;
    lanac_sad++;
    hld(graf[cvor][i].first, cvor);
  }
}
void update(int x, node v) {
  x += off;
  tur[x] = v;
  for (x = x / 2; x > 0; x /= 2) tur[x] = merge(tur[2 * x], tur[2 * x + 1]);
}
node query(int cvor, int a, int b, int lo, int hi) {
  if (a > hi || b < lo) return node();
  if (a >= lo && b <= hi) return tur[cvor];
  return merge(query(2 * cvor, a, (a + b) / 2, lo, hi),
               query(2 * cvor + 1, (a + b) / 2 + 1, b, lo, hi));
}
void postavi() {
  for (off = 1; off < n; off *= 2)
    ;
  for (int i = 0; i < off; i++) update(i, node(1, 0, 0, 0));
}
int lca(int a, int b) {
  if (moj_lanac[a] == moj_lanac[b]) {
    if (dubina[a] < dubina[b]) return a;
    return b;
  }
  if (dubina[glava[moj_lanac[a]]] > dubina[glava[moj_lanac[b]]])
    return lca(tata[glava[moj_lanac[a]]], b);
  return lca(a, tata[glava[moj_lanac[b]]]);
}
node up(int vrh, int x) {
  if (moj_lanac[vrh] == moj_lanac[x])
    return query(1, 0, off - 1, pos[vrh] + 1, pos[x]);
  return merge(up(vrh, tata[glava[moj_lanac[x]]]),
               query(1, 0, off - 1, pos[glava[moj_lanac[x]]], pos[x]));
}
int upit(int a, int b) {
  int x = lca(a, b);
  node u = up(x, a);
  node v = up(x, b);
  swap(u.prefix, u.suffix);
  node t = merge(u, v);
  t = merge(node(1, 0, 0, 0), t);
  t = merge(t, node(1, 0, 0, 0));
  return t.x;
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n - 1; i++) scanf("%d", &f[i]);
  for (int i = 1; i <= n - 1; i++) {
    int a, b, x;
    scanf("%d %d %d", &a, &b, &x);
    graf[a].push_back(pair<int, int>(b, i));
    graf[b].push_back(pair<int, int>(a, i));
    cijena[i] = x;
  }
  izgradi_podstabla(1, -1, 1);
  hld(1, -1);
  for (int i = 1; i <= n - 1; i++) event.push_back(struktura(cijena[i], 0, i));
  for (int i = 0; i < q; i++) {
    int a, b, x;
    scanf("%d %d %d", &a, &b, &x);
    event.push_back(struktura(x, 1, a, b, i));
  }
  postavi();
  sort(event.begin(), event.end(), cmp);
  for (int i = 0; i < event.size(); i++) {
    struktura t = event[i];
    if (t.tip == 0)
      update(pos[brid[t.a]], node(1, 0, 1, 1));
    else if (t.tip == 1)
      rj[t.indeks] = upit(t.a, t.b);
  }
  for (int i = 0; i < q; i++) printf("%d\n", rj[i]);
  return 0;
}

### Prompt

Generate 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;
const int MAXN = 100010, OFF = (1 << 19) + 10;
struct struktura {
  int vrijeme, tip, a, b, indeks;
  struktura() {}
  struktura(int _vrijeme, int _tip, int _a, int _b = 0, int _indeks = 0) {
    vrijeme = _vrijeme;
    tip = _tip;
    a = _a;
    b = _b;
    indeks = _indeks;
  }
};
int cmp(struktura prva, struktura druga) {
  if (prva.vrijeme != druga.vrijeme) return prva.vrijeme > druga.vrijeme;
  if (prva.tip != druga.tip) return prva.tip < druga.tip;
  if (prva.a != druga.a) return prva.a < druga.a;
  if (prva.b != druga.b) return prva.b < druga.b;
  return prva.indeks < druga.indeks;
}
struct node {
  int velicina, x, prefix, suffix;
  node(int _velicina = 0, int _x = 0, int _prefix = 0, int _suffix = 0) {
    velicina = _velicina;
    x = _x;
    prefix = _prefix;
    suffix = _suffix;
  }
};
int f[MAXN];
node merge(node a, node b) {
  node ret;
  ret.velicina = a.velicina + b.velicina;
  ret.x = a.x + b.x;
  if (a.velicina == 0 && b.velicina == 0)
    return a;
  else if (a.velicina == 0)
    return b;
  else if (b.velicina == 0)
    return a;
  if (a.prefix == a.velicina && b.prefix == b.velicina) {
    ret.prefix = ret.suffix = ret.velicina;
  } else if (a.prefix == a.velicina) {
    ret.prefix = a.velicina + b.prefix;
    ret.suffix = b.suffix;
  } else if (b.prefix == b.velicina) {
    ret.prefix = a.prefix;
    ret.suffix = a.suffix + b.velicina;
  } else {
    ret.prefix = a.prefix;
    ret.suffix = b.suffix;
    ret.x += f[a.suffix + b.prefix];
  }
  return ret;
}
int n, q, off;
int rj[MAXN];
int cijena[MAXN], brid[MAXN];
int dubina[MAXN], tata[MAXN], podstablo[MAXN];
int moj_lanac[MAXN], glava[MAXN], pos[MAXN];
int pos_sad = -1, lanac_sad = 1;
vector<pair<int, int> > graf[MAXN];
vector<struktura> event;
node tur[OFF];
int izgradi_podstabla(int cvor, int roditelj, int d) {
  dubina[cvor] = d;
  podstablo[cvor] = 1;
  for (int i = 0; i < graf[cvor].size(); i++) {
    if (graf[cvor][i].first == roditelj) continue;
    brid[graf[cvor][i].second] = graf[cvor][i].first;
    tata[graf[cvor][i].first] = cvor;
    podstablo[cvor] += izgradi_podstabla(graf[cvor][i].first, cvor, d + 1);
  }
  return podstablo[cvor];
}
void hld(int cvor, int roditelj) {
  if (!glava[lanac_sad]) glava[lanac_sad] = cvor;
  pos[cvor] = ++pos_sad;
  moj_lanac[cvor] = lanac_sad;
  int maksi = -1, koji = -1;
  for (int i = 0; i < graf[cvor].size(); i++) {
    if (graf[cvor][i].first == roditelj) continue;
    if (podstablo[graf[cvor][i].first] > maksi) {
      maksi = podstablo[graf[cvor][i].first];
      koji = i;
    }
  }
  if (koji >= 0) hld(graf[cvor][koji].first, cvor);
  for (int i = 0; i < graf[cvor].size(); i++) {
    if (graf[cvor][i].first == roditelj) continue;
    if (koji == i) continue;
    lanac_sad++;
    hld(graf[cvor][i].first, cvor);
  }
}
void update(int x, node v) {
  x += off;
  tur[x] = v;
  for (x = x / 2; x > 0; x /= 2) tur[x] = merge(tur[2 * x], tur[2 * x + 1]);
}
node query(int cvor, int a, int b, int lo, int hi) {
  if (a > hi || b < lo) return node();
  if (a >= lo && b <= hi) return tur[cvor];
  return merge(query(2 * cvor, a, (a + b) / 2, lo, hi),
               query(2 * cvor + 1, (a + b) / 2 + 1, b, lo, hi));
}
void postavi() {
  for (off = 1; off < n; off *= 2)
    ;
  for (int i = 0; i < off; i++) update(i, node(1, 0, 0, 0));
}
int lca(int a, int b) {
  if (moj_lanac[a] == moj_lanac[b]) {
    if (dubina[a] < dubina[b]) return a;
    return b;
  }
  if (dubina[glava[moj_lanac[a]]] > dubina[glava[moj_lanac[b]]])
    return lca(tata[glava[moj_lanac[a]]], b);
  return lca(a, tata[glava[moj_lanac[b]]]);
}
node up(int vrh, int x) {
  if (moj_lanac[vrh] == moj_lanac[x])
    return query(1, 0, off - 1, pos[vrh] + 1, pos[x]);
  return merge(up(vrh, tata[glava[moj_lanac[x]]]),
               query(1, 0, off - 1, pos[glava[moj_lanac[x]]], pos[x]));
}
int upit(int a, int b) {
  int x = lca(a, b);
  node u = up(x, a);
  node v = up(x, b);
  swap(u.prefix, u.suffix);
  node t = merge(u, v);
  t = merge(node(1, 0, 0, 0), t);
  t = merge(t, node(1, 0, 0, 0));
  return t.x;
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n - 1; i++) scanf("%d", &f[i]);
  for (int i = 1; i <= n - 1; i++) {
    int a, b, x;
    scanf("%d %d %d", &a, &b, &x);
    graf[a].push_back(pair<int, int>(b, i));
    graf[b].push_back(pair<int, int>(a, i));
    cijena[i] = x;
  }
  izgradi_podstabla(1, -1, 1);
  hld(1, -1);
  for (int i = 1; i <= n - 1; i++) event.push_back(struktura(cijena[i], 0, i));
  for (int i = 0; i < q; i++) {
    int a, b, x;
    scanf("%d %d %d", &a, &b, &x);
    event.push_back(struktura(x, 1, a, b, i));
  }
  postavi();
  sort(event.begin(), event.end(), cmp);
  for (int i = 0; i < event.size(); i++) {
    struktura t = event[i];
    if (t.tip == 0)
      update(pos[brid[t.a]], node(1, 0, 1, 1));
    else if (t.tip == 1)
      rj[t.indeks] = upit(t.a, t.b);
  }
  for (int i = 0; i < q; i++) printf("%d\n", rj[i]);
  return 0;
}

```