#include <bits/stdc++.h>
using namespace std;
const int inft = 1000000009;
const int MAXN = 100005;
namespace LCAO {
const int N = 100005, P = N;
vector<int> kraw[N];
vector<pair<int, int> > pytania[N];
int odpowiedzi[P];
int kolor[N], fu[N], przodek[N];
int fufind(int first) {
  return fu[first] < 0 ? first : fu[first] = fufind(fu[first]);
}
void DfsTarjan(int first, int parent) {
  kolor[first] = 1;
  fu[first] = -1;
  przodek[first] = first;
  for (typeof((kraw[first]).begin()) it = (kraw[first]).begin();
       it != (kraw[first]).end(); ++it)
    if (*it != parent) {
      DfsTarjan(*it, first);
      int a = fufind(first), b = fufind(*it);
      if (fu[a] < fu[b]) swap(a, b);
      fu[b] += fu[a];
      fu[a] = b;
      przodek[b] = first;
    }
  for (typeof((pytania[first]).begin()) it = (pytania[first]).begin();
       it != (pytania[first]).end(); ++it)
    if (kolor[it->first] == 2) {
      int lca = przodek[fufind(it->first)];
      odpowiedzi[it->second] = lca;
    }
  kolor[first] = 2;
}
void dodaj_krawedz(int a, int b) {
  kraw[a].push_back(b);
  kraw[b].push_back(a);
}
int nr = 0;
void dodaj_pytanie(int a, int b) {
  if (a == b)
    odpowiedzi[nr] = a;
  else {
    pytania[a].push_back(pair<int, int>(b, nr));
    pytania[b].push_back(pair<int, int>(a, nr));
  }
  nr++;
}
void czysc(int n = N) {
  for (int i = 0; i < (n); ++i)
    kraw[i].clear(), pytania[i].clear(), kolor[i] = 0;
  nr = 0;
}
}  // namespace LCAO
int ff[MAXN];
struct ODP {
  int pocz, kon, dl, wew;
  ODP() { pocz = kon = dl = wew = 0; }
  ODP(int a) {
    pocz = kon = a;
    dl = 1;
    wew = 0;
  }
  void wypisz() { ; }
};
ODP obroc(ODP A) {
  swap(A.pocz, A.kon);
  return A;
}
ODP scal(ODP A, ODP B) {
  ODP C;
  if (A.pocz == A.dl && B.pocz == B.dl) {
    C.pocz = C.kon = C.dl = A.dl + B.dl;
    C.wew = 0;
  } else if (A.pocz == A.dl) {
    C = B;
    C.pocz += A.pocz;
    C.dl += A.dl;
  } else if (B.pocz == B.dl) {
    C = A;
    C.kon += B.dl;
    C.dl += B.dl;
  } else {
    C.pocz = A.pocz;
    C.kon = B.kon;
    C.dl = A.dl + B.dl;
    C.wew = A.wew + B.wew + ff[A.kon + B.pocz];
  }
  return C;
}
vector<int> V[MAXN];
vector<pair<int, pair<int, int> > > EE;
int ANS[MAXN];
int n;
int siz[MAXN], par[MAXN];
void dfs(int u, int pr) {
  siz[u] = 1;
  par[u] = pr;
  for (typeof((V[u]).begin()) it = (V[u]).begin(); it != (V[u]).end(); ++it)
    if (*it != pr) {
      dfs(*it, u);
      siz[u] += siz[*it];
    }
}
struct sciezka {
  int d, czubek, baza;
  vector<ODP> D;
  void zbuduj() {
    baza = 1;
    while (baza < d) baza *= 2;
    D.resize(2 * baza, ODP(0));
    for (int i = baza - 1; i; --i) D[i] = scal(D[2 * i], D[2 * i + 1]);
  }
  void dodaj(int a) {
    a += baza;
    D[a] = ODP(1);
    a /= 2;
    while (a) {
      D[a] = scal(D[2 * a], D[2 * a + 1]);
      a /= 2;
    }
  }
  ODP licz(int a, int b) {
    if (a == b) return ODP();
    a += baza + 1;
    b += baza;
    ODP le = D[a], pr = D[b];
    if (a == b) return le;
    while (a / 2 != b / 2) {
      if (a % 2 == 0) le = scal(le, D[a + 1]);
      if (b % 2 == 1) pr = scal(D[b - 1], pr);
      a /= 2;
      b /= 2;
    }
    return obroc(scal(le, pr));
  }
};
sciezka SS[MAXN];
int CSC[MAXN];
int TAM[MAXN];
ODP GORA[MAXN];
int NUMERY = 0;
void sciezki(int u, int pr, int ktora, int ja) {
  CSC[u] = ktora;
  TAM[u] = ja;
  ++SS[ktora].d;
  if (ja == 0) SS[ktora].czubek = u;
  int best = -1;
  for (typeof((V[u]).begin()) it = (V[u]).begin(); it != (V[u]).end(); ++it)
    if (*it != pr && (best == -1 || siz[*it] > siz[best])) best = *it;
  for (typeof((V[u]).begin()) it = (V[u]).begin(); it != (V[u]).end(); ++it)
    if (*it != pr) {
      if (*it == best)
        sciezki(*it, u, ktora, ja + 1);
      else
        sciezki(*it, u, NUMERY++, 0);
    }
}
void prep() {
  dfs(0, -1);
  sciezki(0, -1, NUMERY++, 0);
  for (int i = 0; i < (NUMERY); ++i) SS[i].zbuduj();
}
void dodaj(int a, int b) {
  if (par[b] == a) swap(a, b);
  if (TAM[a] == 0)
    GORA[a] = ODP(1);
  else
    SS[CSC[a]].dodaj(TAM[a]);
}
ODP licz(int a, int b) {
  ODP ret;
  while (CSC[a] != CSC[b]) {
    ret = scal(ret, SS[CSC[a]].licz(0, TAM[a]));
    a = SS[CSC[a]].czubek;
    ret = scal(ret, GORA[a]);
    a = par[a];
  }
  ret = scal(ret, SS[CSC[a]].licz(TAM[b], TAM[a]));
  return ret;
}
int PYT[MAXN][2];
int main() {
  int q;
  scanf("%d%d", &n, &q);
  for (int i = 0; i < (n - 1); ++i) scanf("%d", &ff[i + 1]);
  for (int i = 0; i < (n - 1); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    --a;
    --b;
    LCAO::kraw[a].push_back(b);
    LCAO::kraw[b].push_back(a);
    V[a].push_back(b);
    V[b].push_back(a);
    EE.push_back(make_pair(c, pair<int, int>(a, b)));
  }
  for (int i = 0; i < (q); ++i) {
    int u, v, l;
    scanf("%d%d%d", &u, &v, &l);
    --u;
    --v;
    LCAO::dodaj_pytanie(u, v);
    PYT[i][0] = u;
    PYT[i][1] = v;
    EE.push_back(make_pair(l, pair<int, int>(-1, i)));
  }
  LCAO::DfsTarjan(0, -1);
  for (int i = 0; i < (n); ++i) GORA[i] = ODP(0);
  sort((EE).begin(), (EE).end());
  reverse((EE).begin(), (EE).end());
  prep();
  for (typeof((EE).begin()) it = (EE).begin(); it != (EE).end(); ++it) {
    if (it->second.first == -1) {
      int nr = it->second.second;
      int lca = LCAO::odpowiedzi[nr];
      ODP A = licz(PYT[nr][0], lca);
      ODP B = obroc(licz(PYT[nr][1], lca));
      A.wypisz();
      B.wypisz();
      ODP C = scal(A, B);
      int ret = C.wew;
      ret += ff[C.pocz];
      ret += ff[C.kon];
      if (C.pocz == C.dl) ret -= ff[C.kon];
      ANS[nr] = ret;
    } else
      dodaj((it->second).first, (it->second).second);
  }
  for (int i = 0; i < (q); ++i) printf("%d\n", ANS[i]);
  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 inft = 1000000009;
const int MAXN = 100005;
namespace LCAO {
const int N = 100005, P = N;
vector<int> kraw[N];
vector<pair<int, int> > pytania[N];
int odpowiedzi[P];
int kolor[N], fu[N], przodek[N];
int fufind(int first) {
  return fu[first] < 0 ? first : fu[first] = fufind(fu[first]);
}
void DfsTarjan(int first, int parent) {
  kolor[first] = 1;
  fu[first] = -1;
  przodek[first] = first;
  for (typeof((kraw[first]).begin()) it = (kraw[first]).begin();
       it != (kraw[first]).end(); ++it)
    if (*it != parent) {
      DfsTarjan(*it, first);
      int a = fufind(first), b = fufind(*it);
      if (fu[a] < fu[b]) swap(a, b);
      fu[b] += fu[a];
      fu[a] = b;
      przodek[b] = first;
    }
  for (typeof((pytania[first]).begin()) it = (pytania[first]).begin();
       it != (pytania[first]).end(); ++it)
    if (kolor[it->first] == 2) {
      int lca = przodek[fufind(it->first)];
      odpowiedzi[it->second] = lca;
    }
  kolor[first] = 2;
}
void dodaj_krawedz(int a, int b) {
  kraw[a].push_back(b);
  kraw[b].push_back(a);
}
int nr = 0;
void dodaj_pytanie(int a, int b) {
  if (a == b)
    odpowiedzi[nr] = a;
  else {
    pytania[a].push_back(pair<int, int>(b, nr));
    pytania[b].push_back(pair<int, int>(a, nr));
  }
  nr++;
}
void czysc(int n = N) {
  for (int i = 0; i < (n); ++i)
    kraw[i].clear(), pytania[i].clear(), kolor[i] = 0;
  nr = 0;
}
}  // namespace LCAO
int ff[MAXN];
struct ODP {
  int pocz, kon, dl, wew;
  ODP() { pocz = kon = dl = wew = 0; }
  ODP(int a) {
    pocz = kon = a;
    dl = 1;
    wew = 0;
  }
  void wypisz() { ; }
};
ODP obroc(ODP A) {
  swap(A.pocz, A.kon);
  return A;
}
ODP scal(ODP A, ODP B) {
  ODP C;
  if (A.pocz == A.dl && B.pocz == B.dl) {
    C.pocz = C.kon = C.dl = A.dl + B.dl;
    C.wew = 0;
  } else if (A.pocz == A.dl) {
    C = B;
    C.pocz += A.pocz;
    C.dl += A.dl;
  } else if (B.pocz == B.dl) {
    C = A;
    C.kon += B.dl;
    C.dl += B.dl;
  } else {
    C.pocz = A.pocz;
    C.kon = B.kon;
    C.dl = A.dl + B.dl;
    C.wew = A.wew + B.wew + ff[A.kon + B.pocz];
  }
  return C;
}
vector<int> V[MAXN];
vector<pair<int, pair<int, int> > > EE;
int ANS[MAXN];
int n;
int siz[MAXN], par[MAXN];
void dfs(int u, int pr) {
  siz[u] = 1;
  par[u] = pr;
  for (typeof((V[u]).begin()) it = (V[u]).begin(); it != (V[u]).end(); ++it)
    if (*it != pr) {
      dfs(*it, u);
      siz[u] += siz[*it];
    }
}
struct sciezka {
  int d, czubek, baza;
  vector<ODP> D;
  void zbuduj() {
    baza = 1;
    while (baza < d) baza *= 2;
    D.resize(2 * baza, ODP(0));
    for (int i = baza - 1; i; --i) D[i] = scal(D[2 * i], D[2 * i + 1]);
  }
  void dodaj(int a) {
    a += baza;
    D[a] = ODP(1);
    a /= 2;
    while (a) {
      D[a] = scal(D[2 * a], D[2 * a + 1]);
      a /= 2;
    }
  }
  ODP licz(int a, int b) {
    if (a == b) return ODP();
    a += baza + 1;
    b += baza;
    ODP le = D[a], pr = D[b];
    if (a == b) return le;
    while (a / 2 != b / 2) {
      if (a % 2 == 0) le = scal(le, D[a + 1]);
      if (b % 2 == 1) pr = scal(D[b - 1], pr);
      a /= 2;
      b /= 2;
    }
    return obroc(scal(le, pr));
  }
};
sciezka SS[MAXN];
int CSC[MAXN];
int TAM[MAXN];
ODP GORA[MAXN];
int NUMERY = 0;
void sciezki(int u, int pr, int ktora, int ja) {
  CSC[u] = ktora;
  TAM[u] = ja;
  ++SS[ktora].d;
  if (ja == 0) SS[ktora].czubek = u;
  int best = -1;
  for (typeof((V[u]).begin()) it = (V[u]).begin(); it != (V[u]).end(); ++it)
    if (*it != pr && (best == -1 || siz[*it] > siz[best])) best = *it;
  for (typeof((V[u]).begin()) it = (V[u]).begin(); it != (V[u]).end(); ++it)
    if (*it != pr) {
      if (*it == best)
        sciezki(*it, u, ktora, ja + 1);
      else
        sciezki(*it, u, NUMERY++, 0);
    }
}
void prep() {
  dfs(0, -1);
  sciezki(0, -1, NUMERY++, 0);
  for (int i = 0; i < (NUMERY); ++i) SS[i].zbuduj();
}
void dodaj(int a, int b) {
  if (par[b] == a) swap(a, b);
  if (TAM[a] == 0)
    GORA[a] = ODP(1);
  else
    SS[CSC[a]].dodaj(TAM[a]);
}
ODP licz(int a, int b) {
  ODP ret;
  while (CSC[a] != CSC[b]) {
    ret = scal(ret, SS[CSC[a]].licz(0, TAM[a]));
    a = SS[CSC[a]].czubek;
    ret = scal(ret, GORA[a]);
    a = par[a];
  }
  ret = scal(ret, SS[CSC[a]].licz(TAM[b], TAM[a]));
  return ret;
}
int PYT[MAXN][2];
int main() {
  int q;
  scanf("%d%d", &n, &q);
  for (int i = 0; i < (n - 1); ++i) scanf("%d", &ff[i + 1]);
  for (int i = 0; i < (n - 1); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    --a;
    --b;
    LCAO::kraw[a].push_back(b);
    LCAO::kraw[b].push_back(a);
    V[a].push_back(b);
    V[b].push_back(a);
    EE.push_back(make_pair(c, pair<int, int>(a, b)));
  }
  for (int i = 0; i < (q); ++i) {
    int u, v, l;
    scanf("%d%d%d", &u, &v, &l);
    --u;
    --v;
    LCAO::dodaj_pytanie(u, v);
    PYT[i][0] = u;
    PYT[i][1] = v;
    EE.push_back(make_pair(l, pair<int, int>(-1, i)));
  }
  LCAO::DfsTarjan(0, -1);
  for (int i = 0; i < (n); ++i) GORA[i] = ODP(0);
  sort((EE).begin(), (EE).end());
  reverse((EE).begin(), (EE).end());
  prep();
  for (typeof((EE).begin()) it = (EE).begin(); it != (EE).end(); ++it) {
    if (it->second.first == -1) {
      int nr = it->second.second;
      int lca = LCAO::odpowiedzi[nr];
      ODP A = licz(PYT[nr][0], lca);
      ODP B = obroc(licz(PYT[nr][1], lca));
      A.wypisz();
      B.wypisz();
      ODP C = scal(A, B);
      int ret = C.wew;
      ret += ff[C.pocz];
      ret += ff[C.kon];
      if (C.pocz == C.dl) ret -= ff[C.kon];
      ANS[nr] = ret;
    } else
      dodaj((it->second).first, (it->second).second);
  }
  for (int i = 0; i < (q); ++i) printf("%d\n", ANS[i]);
  return 0;
}

```