#include <bits/stdc++.h>
using namespace std;
const int inft = 1000000009;
const int mod = 1000000007;
const int MAXN = 100006;
int f[MAXN];
const int N = MAXN, P = MAXN;
vector<int> G[N];
pair<int, int> E[MAXN], Q[MAXN];
int C[MAXN];
namespace LCAO {
vector<pair<int, int> > pyt[N];
int LCA[P];
int kolor[N], REP[N], przodek[N];
int find(int first) {
  return REP[first] < 0 ? first : REP[first] = find(REP[first]);
}
void DfsTarjan(int first, int par) {
  kolor[first] = 1;
  REP[first] = -1;
  przodek[first] = first;
  for (typeof((G[first]).begin()) it = (G[first]).begin();
       it != (G[first]).end(); ++it)
    if (*it != par) {
      DfsTarjan(*it, first);
      int a = find(first), b = find(*it);
      if (REP[a] < REP[b]) swap(a, b);
      REP[b] += REP[a];
      REP[a] = b;
      przodek[b] = first;
    }
  for (typeof((pyt[first]).begin()) it = (pyt[first]).begin();
       it != (pyt[first]).end(); ++it)
    if (kolor[it->first] == 2) {
      int lca = przodek[find(it->first)];
      LCA[it->second] = lca;
    }
  kolor[first] = 2;
}
void dodaj_krawedz(int a, int b) {
  G[a].push_back(b);
  G[b].push_back(a);
}
int nr = 0;
void dodaj_pytanie(int a, int b) {
  if (a == b)
    LCA[nr] = a;
  else {
    pyt[a].push_back(pair<int, int>(b, nr));
    pyt[b].push_back(pair<int, int>(a, nr));
  }
  nr++;
}
void czysc(int n = N) {
  for (int i = 0; i < (n); ++i) G[i].clear(), pyt[i].clear(), kolor[i] = 0;
  nr = 0;
}
}  // namespace LCAO
pair<int, pair<int, int> > rev(pair<int, pair<int, int> > a) {
  return pair<int, pair<int, int> >(
      a.first, pair<int, int>(a.second.second, a.second.first));
}
pair<int, pair<int, int> > merge(pair<int, pair<int, int> > t1,
                                 pair<int, pair<int, int> > t2) {
  ;
  if (t1.first == -inft) {
    if (t2.first == -inft) {
      ;
      return pair<int, pair<int, int> >(
          -inft, pair<int, int>(t1.second.first + t2.second.first,
                                t1.second.first + t2.second.first));
    } else {
      ;
      return pair<int, pair<int, int> >(
          t2.first,
          pair<int, int>(t1.second.first + t2.second.first, t2.second.second));
    }
  } else if (t2.first == -inft) {
    ;
    return pair<int, pair<int, int> >(
        t1.first,
        pair<int, int>(t1.second.first, t1.second.second + t2.second.second));
  };
  return pair<int, pair<int, int> >(
      t1.first + t2.first + f[t1.second.second + t2.second.first],
      pair<int, int>(t1.second.first, t2.second.second));
}
int eval(pair<int, pair<int, int> > t1) {
  ;
  if (t1.first == -inft) return f[t1.second.first];
  return f[t1.second.first] + f[t1.second.second] + t1.first;
}
struct drzewo {
  int T;
  vector<pair<int, pair<int, int> > > drz;
  void init(int n) {
    T = 1;
    while (T < n) T *= 2;
    drz.resize(2 * T, pair<int, pair<int, int> >(0, pair<int, int>(0, 0)));
  }
  void update(int a, int b) {
    assert(a == b);
    a += T;
    drz[a] = pair<int, pair<int, int> >(-inft, pair<int, int>(1, 1));
    a /= 2;
    while (a) {
      drz[a] = merge(drz[2 * a], drz[2 * a + 1]);
      a /= 2;
    }
  }
  pair<int, pair<int, int> > get(int a, int b) {
    pair<int, pair<int, int> > ret1 =
        pair<int, pair<int, int> >(-inft, pair<int, int>(0, 0));
    pair<int, pair<int, int> > ret2 =
        pair<int, pair<int, int> >(-inft, pair<int, int>(0, 0));
    a += T;
    b += T;
    while (a <= b) {
      if (a % 2 == 1) {
        ret1 = merge(ret1, drz[a]);
        a++;
      }
      if (b % 2 == 0) {
        ret2 = merge(drz[b], ret2);
        b--;
      }
      a /= 2;
      b /= 2;
    }
    return merge(ret1, ret2);
  }
};
namespace HLD {
drzewo CS[N];
int nrc[N];
int ind[N];
int hop[N];
int siz[N];
int sciezek;
pair<int, pair<int, int> > get(int a, int anc) {
  ;
  pair<int, pair<int, int> > ret(-inft, pair<int, int>(0, 0));
  while (nrc[a] != nrc[anc]) {
    ret = merge(ret, rev(CS[nrc[a]].get(0, ind[a])));
    a = hop[nrc[a]];
  }
  ret = merge(ret, rev(CS[nrc[a]].get(ind[anc] + 1, ind[a])));
  ;
  return ret;
}
void update(int a, int anc) {
  ;
  while (nrc[a] != nrc[anc]) {
    CS[nrc[a]].update(0, ind[a]);
    a = hop[nrc[a]];
  }
  CS[nrc[a]].update(ind[anc], ind[a]);
}
int rozm(int u, int pr) {
  siz[u] = 1;
  for (typeof((G[u]).begin()) it = (G[u]).begin(); it != (G[u]).end(); ++it)
    if (*it != pr) siz[u] += rozm(*it, u);
  return siz[u];
}
void ciezka(int u, int pr, int csc, int index) {
  nrc[u] = csc;
  ind[u] = index;
  int dz = -1;
  for (typeof((G[u]).begin()) it = (G[u]).begin(); it != (G[u]).end(); ++it)
    if (*it != pr && (dz == -1 || siz[*it] > siz[dz])) dz = *it;
  for (typeof((G[u]).begin()) it = (G[u]).begin(); it != (G[u]).end(); ++it)
    if (*it == dz)
      ciezka(*it, u, csc, index + 1);
    else if (*it != pr) {
      hop[sciezek++] = u;
      ciezka(*it, u, sciezek - 1, 0);
    }
  if (dz == -1) {
    CS[csc].init(index + 1);
  }
}
void init(int root) {
  rozm(root, -1);
  sciezek = 1;
  hop[0] = -1;
  ciezka(root, -1, 0, 0);
}
}  // namespace HLD
void solve() {
  int n, q;
  scanf("%d%d", &n, &q);
  f[0] = 0;
  for (int i = 0; i < (n - 1); ++i) {
    scanf("%d", &f[i + 1]);
  }
  vector<pair<int, int> > EV;
  for (int i = 0; i < (n - 1); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    LCAO::dodaj_krawedz(a, b);
    E[i] = pair<int, int>(a, b);
    EV.push_back(pair<int, int>(c + 1, -(i + 1)));
  }
  for (int i = 0; i < (q); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    LCAO::dodaj_pytanie(a, b);
    Q[i] = pair<int, int>(a, b);
    EV.push_back(pair<int, int>(c, i));
  }
  vector<int> ANS(q);
  LCAO::DfsTarjan(0, -1);
  HLD::init(0);
  for (int i = 0; i < (n - 1); ++i)
    if (HLD::siz[E[i].first] > HLD::siz[E[i].second])
      swap(E[i].first, E[i].second);
  sort((EV).begin(), (EV).end());
  reverse((EV).begin(), (EV).end());
  for (typeof((EV).begin()) it = (EV).begin(); it != (EV).end(); ++it) {
    if (it->second >= 0) {
      ;
      int u = LCAO::LCA[it->second], u1 = Q[it->second].first,
          u2 = Q[it->second].second;
      pair<int, pair<int, int> > t1 = HLD::get(u1, u), t2 = HLD::get(u2, u);
      t1 = merge(t1, rev(t2));
      ANS[it->second] = eval(t1);
    } else {
      int u = -it->second - 1;
      ;
      HLD::update(E[u].first, E[u].first);
    }
  }
  for (typeof((ANS).begin()) it = (ANS).begin(); it != (ANS).end(); ++it)
    printf("%d\n", *it);
}
int main() {
  int te = 1;
  for (int ti = 0; ti < (te); ++ti) solve();
  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 mod = 1000000007;
const int MAXN = 100006;
int f[MAXN];
const int N = MAXN, P = MAXN;
vector<int> G[N];
pair<int, int> E[MAXN], Q[MAXN];
int C[MAXN];
namespace LCAO {
vector<pair<int, int> > pyt[N];
int LCA[P];
int kolor[N], REP[N], przodek[N];
int find(int first) {
  return REP[first] < 0 ? first : REP[first] = find(REP[first]);
}
void DfsTarjan(int first, int par) {
  kolor[first] = 1;
  REP[first] = -1;
  przodek[first] = first;
  for (typeof((G[first]).begin()) it = (G[first]).begin();
       it != (G[first]).end(); ++it)
    if (*it != par) {
      DfsTarjan(*it, first);
      int a = find(first), b = find(*it);
      if (REP[a] < REP[b]) swap(a, b);
      REP[b] += REP[a];
      REP[a] = b;
      przodek[b] = first;
    }
  for (typeof((pyt[first]).begin()) it = (pyt[first]).begin();
       it != (pyt[first]).end(); ++it)
    if (kolor[it->first] == 2) {
      int lca = przodek[find(it->first)];
      LCA[it->second] = lca;
    }
  kolor[first] = 2;
}
void dodaj_krawedz(int a, int b) {
  G[a].push_back(b);
  G[b].push_back(a);
}
int nr = 0;
void dodaj_pytanie(int a, int b) {
  if (a == b)
    LCA[nr] = a;
  else {
    pyt[a].push_back(pair<int, int>(b, nr));
    pyt[b].push_back(pair<int, int>(a, nr));
  }
  nr++;
}
void czysc(int n = N) {
  for (int i = 0; i < (n); ++i) G[i].clear(), pyt[i].clear(), kolor[i] = 0;
  nr = 0;
}
}  // namespace LCAO
pair<int, pair<int, int> > rev(pair<int, pair<int, int> > a) {
  return pair<int, pair<int, int> >(
      a.first, pair<int, int>(a.second.second, a.second.first));
}
pair<int, pair<int, int> > merge(pair<int, pair<int, int> > t1,
                                 pair<int, pair<int, int> > t2) {
  ;
  if (t1.first == -inft) {
    if (t2.first == -inft) {
      ;
      return pair<int, pair<int, int> >(
          -inft, pair<int, int>(t1.second.first + t2.second.first,
                                t1.second.first + t2.second.first));
    } else {
      ;
      return pair<int, pair<int, int> >(
          t2.first,
          pair<int, int>(t1.second.first + t2.second.first, t2.second.second));
    }
  } else if (t2.first == -inft) {
    ;
    return pair<int, pair<int, int> >(
        t1.first,
        pair<int, int>(t1.second.first, t1.second.second + t2.second.second));
  };
  return pair<int, pair<int, int> >(
      t1.first + t2.first + f[t1.second.second + t2.second.first],
      pair<int, int>(t1.second.first, t2.second.second));
}
int eval(pair<int, pair<int, int> > t1) {
  ;
  if (t1.first == -inft) return f[t1.second.first];
  return f[t1.second.first] + f[t1.second.second] + t1.first;
}
struct drzewo {
  int T;
  vector<pair<int, pair<int, int> > > drz;
  void init(int n) {
    T = 1;
    while (T < n) T *= 2;
    drz.resize(2 * T, pair<int, pair<int, int> >(0, pair<int, int>(0, 0)));
  }
  void update(int a, int b) {
    assert(a == b);
    a += T;
    drz[a] = pair<int, pair<int, int> >(-inft, pair<int, int>(1, 1));
    a /= 2;
    while (a) {
      drz[a] = merge(drz[2 * a], drz[2 * a + 1]);
      a /= 2;
    }
  }
  pair<int, pair<int, int> > get(int a, int b) {
    pair<int, pair<int, int> > ret1 =
        pair<int, pair<int, int> >(-inft, pair<int, int>(0, 0));
    pair<int, pair<int, int> > ret2 =
        pair<int, pair<int, int> >(-inft, pair<int, int>(0, 0));
    a += T;
    b += T;
    while (a <= b) {
      if (a % 2 == 1) {
        ret1 = merge(ret1, drz[a]);
        a++;
      }
      if (b % 2 == 0) {
        ret2 = merge(drz[b], ret2);
        b--;
      }
      a /= 2;
      b /= 2;
    }
    return merge(ret1, ret2);
  }
};
namespace HLD {
drzewo CS[N];
int nrc[N];
int ind[N];
int hop[N];
int siz[N];
int sciezek;
pair<int, pair<int, int> > get(int a, int anc) {
  ;
  pair<int, pair<int, int> > ret(-inft, pair<int, int>(0, 0));
  while (nrc[a] != nrc[anc]) {
    ret = merge(ret, rev(CS[nrc[a]].get(0, ind[a])));
    a = hop[nrc[a]];
  }
  ret = merge(ret, rev(CS[nrc[a]].get(ind[anc] + 1, ind[a])));
  ;
  return ret;
}
void update(int a, int anc) {
  ;
  while (nrc[a] != nrc[anc]) {
    CS[nrc[a]].update(0, ind[a]);
    a = hop[nrc[a]];
  }
  CS[nrc[a]].update(ind[anc], ind[a]);
}
int rozm(int u, int pr) {
  siz[u] = 1;
  for (typeof((G[u]).begin()) it = (G[u]).begin(); it != (G[u]).end(); ++it)
    if (*it != pr) siz[u] += rozm(*it, u);
  return siz[u];
}
void ciezka(int u, int pr, int csc, int index) {
  nrc[u] = csc;
  ind[u] = index;
  int dz = -1;
  for (typeof((G[u]).begin()) it = (G[u]).begin(); it != (G[u]).end(); ++it)
    if (*it != pr && (dz == -1 || siz[*it] > siz[dz])) dz = *it;
  for (typeof((G[u]).begin()) it = (G[u]).begin(); it != (G[u]).end(); ++it)
    if (*it == dz)
      ciezka(*it, u, csc, index + 1);
    else if (*it != pr) {
      hop[sciezek++] = u;
      ciezka(*it, u, sciezek - 1, 0);
    }
  if (dz == -1) {
    CS[csc].init(index + 1);
  }
}
void init(int root) {
  rozm(root, -1);
  sciezek = 1;
  hop[0] = -1;
  ciezka(root, -1, 0, 0);
}
}  // namespace HLD
void solve() {
  int n, q;
  scanf("%d%d", &n, &q);
  f[0] = 0;
  for (int i = 0; i < (n - 1); ++i) {
    scanf("%d", &f[i + 1]);
  }
  vector<pair<int, int> > EV;
  for (int i = 0; i < (n - 1); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    LCAO::dodaj_krawedz(a, b);
    E[i] = pair<int, int>(a, b);
    EV.push_back(pair<int, int>(c + 1, -(i + 1)));
  }
  for (int i = 0; i < (q); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    LCAO::dodaj_pytanie(a, b);
    Q[i] = pair<int, int>(a, b);
    EV.push_back(pair<int, int>(c, i));
  }
  vector<int> ANS(q);
  LCAO::DfsTarjan(0, -1);
  HLD::init(0);
  for (int i = 0; i < (n - 1); ++i)
    if (HLD::siz[E[i].first] > HLD::siz[E[i].second])
      swap(E[i].first, E[i].second);
  sort((EV).begin(), (EV).end());
  reverse((EV).begin(), (EV).end());
  for (typeof((EV).begin()) it = (EV).begin(); it != (EV).end(); ++it) {
    if (it->second >= 0) {
      ;
      int u = LCAO::LCA[it->second], u1 = Q[it->second].first,
          u2 = Q[it->second].second;
      pair<int, pair<int, int> > t1 = HLD::get(u1, u), t2 = HLD::get(u2, u);
      t1 = merge(t1, rev(t2));
      ANS[it->second] = eval(t1);
    } else {
      int u = -it->second - 1;
      ;
      HLD::update(E[u].first, E[u].first);
    }
  }
  for (typeof((ANS).begin()) it = (ANS).begin(); it != (ANS).end(); ++it)
    printf("%d\n", *it);
}
int main() {
  int te = 1;
  for (int ti = 0; ti < (te); ++ti) solve();
  return 0;
}

```