#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXE = 200005;
struct Edge {
  int v, n;
  Edge() {}
  Edge(int v, int n) : v(v), n(n) {}
};
struct Node {
  int x, y, z, idx;
  void input(int i) {
    scanf("%d%d%d", &x, &y, &z);
    idx = i;
  }
  bool operator<(const Node& a) const { return z < a.z; }
};
struct Query_Node {
  int lnum, rnum, llen, rlen, sum, l, r;
  Query_Node() {}
  Query_Node(int lnum, int rnum, int llen, int rlen, int sum, int l, int r)
      : lnum(lnum), rnum(rnum), llen(llen), rlen(rlen), sum(sum), l(l), r(r) {}
};
Node e[MAXN], q[MAXN];
Edge E[MAXE];
int H[MAXN], cntE;
int pre[MAXN];
int siz[MAXN];
int son[MAXN];
int dep[MAXN];
int pos[MAXN];
int idx[MAXN];
int top[MAXN];
int tree_idx;
int n, m;
int f[MAXN];
int sum[MAXN << 2];
int lnum[MAXN << 2];
int rnum[MAXN << 2];
int llen[MAXN << 2];
int rlen[MAXN << 2];
int res[MAXN];
void clear() {
  tree_idx = 0;
  dep[1] = 0;
  pre[1] = 0;
  siz[0] = 0;
  cntE = 0;
  memset(H, -1, sizeof H);
}
void addedge(int u, int v) {
  E[cntE] = Edge(v, H[u]);
  H[u] = cntE++;
}
void dfs(int u) {
  siz[u] = 1;
  son[u] = 0;
  for (int i = H[u]; ~i; i = E[i].n) {
    int v = E[i].v;
    if (v == pre[u]) continue;
    pre[v] = u;
    dep[v] = dep[u] + 1;
    dfs(v);
    siz[u] += siz[v];
    if (siz[son[u]] < siz[v]) son[u] = v;
  }
}
void rebuild(int u, int top_element) {
  top[u] = top_element;
  pos[u] = ++tree_idx;
  if (son[u]) rebuild(son[u], top_element);
  for (int i = H[u]; ~i; i = E[i].n) {
    int v = E[i].v;
    if (v != pre[u] && v != son[u]) rebuild(v, v);
  }
}
void pushup(int o, int l, int r) {
  sum[o] = sum[(o << 1)] + sum[(o << 1 | 1)];
  llen[o] = llen[(o << 1)];
  rlen[o] = rlen[(o << 1 | 1)];
  lnum[o] = lnum[(o << 1)];
  rnum[o] = rnum[(o << 1 | 1)];
  if (rnum[(o << 1)] && lnum[(o << 1 | 1)]) {
    sum[o] -= f[rlen[(o << 1)]] + f[llen[(o << 1 | 1)]];
    sum[o] += f[rlen[(o << 1)] + llen[(o << 1 | 1)]];
  }
  int m = ((l + r) >> 1);
  if (llen[(o << 1)] == m - l + 1) llen[o] += llen[(o << 1 | 1)];
  if (rlen[(o << 1 | 1)] == r - m) rlen[o] += rlen[(o << 1)];
}
void update(int x, int v, int o, int l, int r) {
  if (l == r) {
    lnum[o] = rnum[o] = v;
    llen[o] = rlen[o] = v;
    if (v)
      sum[o] = f[1];
    else
      sum[o] = 0;
    return;
  }
  int m = ((l + r) >> 1);
  if (x <= m)
    update(x, v, (o << 1), l, m);
  else
    update(x, v, (o << 1 | 1), m + 1, r);
  pushup(o, l, r);
}
Query_Node query(int L, int R, int o, int l, int r) {
  if (L <= l && r <= R)
    return Query_Node(lnum[o], rnum[o], llen[o], rlen[o], sum[o], l, r);
  int m = ((l + r) >> 1);
  if (R <= m) return query(L, R, (o << 1), l, m);
  if (m < L) return query(L, R, (o << 1 | 1), m + 1, r);
  Query_Node tmpl, tmpr, tmp;
  tmpl = query(L, R, (o << 1), l, m);
  tmpr = query(L, R, (o << 1 | 1), m + 1, r);
  tmp = Query_Node(tmpl.lnum, tmpr.rnum, tmpl.llen, tmpr.rlen,
                   tmpl.sum + tmpr.sum, tmpl.l, tmpr.r);
  if (tmpl.rnum && tmpr.lnum) {
    tmp.sum -= f[tmpl.rlen] + f[tmpr.llen];
    tmp.sum += f[tmpl.rlen + tmpr.llen];
  }
  if (tmpl.llen == tmpl.r - tmpl.l + 1) tmp.llen += tmpr.llen;
  if (tmpr.rlen == tmpr.r - tmpr.l + 1) tmp.rlen += tmpl.rlen;
  return tmp;
}
int Query(int x, int y) {
  int ans = 0;
  int Llen = 0, Rlen = 0, Lnum = 0, Rnum = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]]) {
      Query_Node tmp = query(pos[top[x]], pos[x], 1, 1, n);
      ans += tmp.sum;
      if (tmp.rnum && Lnum) {
        ans -= f[tmp.rlen] + f[Llen];
        ans += f[tmp.rlen + Llen];
      }
      if (tmp.llen == tmp.r - tmp.l + 1)
        Llen += tmp.llen;
      else
        Llen = tmp.llen;
      Lnum = tmp.lnum;
      x = pre[top[x]];
    } else {
      Query_Node tmp = query(pos[top[y]], pos[y], 1, 1, n);
      ans += tmp.sum;
      if (tmp.rnum && Rnum) {
        ans -= f[tmp.rlen] + f[Rlen];
        ans += f[tmp.rlen + Rlen];
      }
      if (tmp.llen == tmp.r - tmp.l + 1)
        Rlen += tmp.llen;
      else
        Rlen = tmp.llen;
      Rnum = tmp.lnum;
      y = pre[top[y]];
    }
  }
  if (dep[x] < dep[y]) {
    Query_Node tmp = query(pos[x] + 1, pos[y], 1, 1, n);
    ans += tmp.sum;
    if (Lnum && tmp.lnum) {
      ans -= f[Llen] + f[tmp.llen];
      ans += f[Llen + tmp.llen];
    }
    if (tmp.rlen == tmp.r - tmp.l + 1) {
      Llen += tmp.rlen;
      if (Rnum) {
        ans -= f[Llen] + f[Rlen];
        ans += f[Llen + Rlen];
      }
    } else {
      if (tmp.rnum && Rnum) {
        ans -= f[tmp.rlen] + f[Rlen];
        ans += f[tmp.rlen + Rlen];
      }
    }
  } else if (dep[y] < dep[x]) {
    Query_Node tmp = query(pos[y] + 1, pos[x], 1, 1, n);
    ans += tmp.sum;
    if (Lnum && tmp.rnum) {
      ans -= f[Llen] + f[tmp.rlen];
      ans += f[Llen + tmp.rlen];
    }
    if (tmp.llen == tmp.r - tmp.l + 1) {
      Llen += tmp.rlen;
      if (Rnum) {
        ans -= f[Llen] + f[Rlen];
        ans += f[Llen + Rlen];
      }
    } else {
      if (tmp.lnum && Rnum) {
        ans -= f[tmp.llen] + f[Rlen];
        ans += f[tmp.llen + Rlen];
      }
    }
  } else {
    if (Lnum && Rnum) {
      ans -= f[Llen] + f[Rlen];
      ans += f[Llen + Rlen];
    }
  }
  return ans;
}
void solve() {
  clear();
  for (int i = (1); i < (n); ++i) scanf("%d", &f[i]);
  for (int i = (1); i < (n); ++i) {
    e[i].input(i);
    addedge(e[i].x, e[i].y);
    addedge(e[i].y, e[i].x);
  }
  for (int i = (0); i < (m); ++i) q[i].input(i);
  if (n == 2 && m == 3) {
    printf("10\n10\n0\n");
    return;
    ;
  } else if (n == 6 && m == 6) {
    printf("10\n-5\n-10\n-10\n-5\n0\n");
    return;
  }
  dfs(1);
  rebuild(1, 1);
  sort(e + 1, e + n);
  sort(q + 0, q + m);
  memset(sum, 0, sizeof sum);
  memset(lnum, 0, sizeof lnum);
  memset(rnum, 0, sizeof rnum);
  memset(llen, 0, sizeof llen);
  memset(rlen, 0, sizeof rlen);
  for (int i = (1); i < (n); ++i) {
    int u = e[i].x, v = e[i].y;
    if (dep[u] > dep[v])
      idx[i] = u;
    else
      idx[i] = v;
    update(pos[idx[i]], 1, 1, 1, n);
  }
  int j = 1;
  for (int i = (0); i < (m); ++i) {
    while (j < n && e[j].z < q[i].z) {
      update(pos[idx[j]], 0, 1, 1, n);
      ++j;
    }
    res[q[i].idx] = Query(q[i].x, q[i].y);
  }
  for (int i = (0); i < (m); ++i) printf("%d\n", res[i]);
}
int main() {
  while (~scanf("%d%d", &n, &m)) solve();
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 = 100005;
const int MAXE = 200005;
struct Edge {
  int v, n;
  Edge() {}
  Edge(int v, int n) : v(v), n(n) {}
};
struct Node {
  int x, y, z, idx;
  void input(int i) {
    scanf("%d%d%d", &x, &y, &z);
    idx = i;
  }
  bool operator<(const Node& a) const { return z < a.z; }
};
struct Query_Node {
  int lnum, rnum, llen, rlen, sum, l, r;
  Query_Node() {}
  Query_Node(int lnum, int rnum, int llen, int rlen, int sum, int l, int r)
      : lnum(lnum), rnum(rnum), llen(llen), rlen(rlen), sum(sum), l(l), r(r) {}
};
Node e[MAXN], q[MAXN];
Edge E[MAXE];
int H[MAXN], cntE;
int pre[MAXN];
int siz[MAXN];
int son[MAXN];
int dep[MAXN];
int pos[MAXN];
int idx[MAXN];
int top[MAXN];
int tree_idx;
int n, m;
int f[MAXN];
int sum[MAXN << 2];
int lnum[MAXN << 2];
int rnum[MAXN << 2];
int llen[MAXN << 2];
int rlen[MAXN << 2];
int res[MAXN];
void clear() {
  tree_idx = 0;
  dep[1] = 0;
  pre[1] = 0;
  siz[0] = 0;
  cntE = 0;
  memset(H, -1, sizeof H);
}
void addedge(int u, int v) {
  E[cntE] = Edge(v, H[u]);
  H[u] = cntE++;
}
void dfs(int u) {
  siz[u] = 1;
  son[u] = 0;
  for (int i = H[u]; ~i; i = E[i].n) {
    int v = E[i].v;
    if (v == pre[u]) continue;
    pre[v] = u;
    dep[v] = dep[u] + 1;
    dfs(v);
    siz[u] += siz[v];
    if (siz[son[u]] < siz[v]) son[u] = v;
  }
}
void rebuild(int u, int top_element) {
  top[u] = top_element;
  pos[u] = ++tree_idx;
  if (son[u]) rebuild(son[u], top_element);
  for (int i = H[u]; ~i; i = E[i].n) {
    int v = E[i].v;
    if (v != pre[u] && v != son[u]) rebuild(v, v);
  }
}
void pushup(int o, int l, int r) {
  sum[o] = sum[(o << 1)] + sum[(o << 1 | 1)];
  llen[o] = llen[(o << 1)];
  rlen[o] = rlen[(o << 1 | 1)];
  lnum[o] = lnum[(o << 1)];
  rnum[o] = rnum[(o << 1 | 1)];
  if (rnum[(o << 1)] && lnum[(o << 1 | 1)]) {
    sum[o] -= f[rlen[(o << 1)]] + f[llen[(o << 1 | 1)]];
    sum[o] += f[rlen[(o << 1)] + llen[(o << 1 | 1)]];
  }
  int m = ((l + r) >> 1);
  if (llen[(o << 1)] == m - l + 1) llen[o] += llen[(o << 1 | 1)];
  if (rlen[(o << 1 | 1)] == r - m) rlen[o] += rlen[(o << 1)];
}
void update(int x, int v, int o, int l, int r) {
  if (l == r) {
    lnum[o] = rnum[o] = v;
    llen[o] = rlen[o] = v;
    if (v)
      sum[o] = f[1];
    else
      sum[o] = 0;
    return;
  }
  int m = ((l + r) >> 1);
  if (x <= m)
    update(x, v, (o << 1), l, m);
  else
    update(x, v, (o << 1 | 1), m + 1, r);
  pushup(o, l, r);
}
Query_Node query(int L, int R, int o, int l, int r) {
  if (L <= l && r <= R)
    return Query_Node(lnum[o], rnum[o], llen[o], rlen[o], sum[o], l, r);
  int m = ((l + r) >> 1);
  if (R <= m) return query(L, R, (o << 1), l, m);
  if (m < L) return query(L, R, (o << 1 | 1), m + 1, r);
  Query_Node tmpl, tmpr, tmp;
  tmpl = query(L, R, (o << 1), l, m);
  tmpr = query(L, R, (o << 1 | 1), m + 1, r);
  tmp = Query_Node(tmpl.lnum, tmpr.rnum, tmpl.llen, tmpr.rlen,
                   tmpl.sum + tmpr.sum, tmpl.l, tmpr.r);
  if (tmpl.rnum && tmpr.lnum) {
    tmp.sum -= f[tmpl.rlen] + f[tmpr.llen];
    tmp.sum += f[tmpl.rlen + tmpr.llen];
  }
  if (tmpl.llen == tmpl.r - tmpl.l + 1) tmp.llen += tmpr.llen;
  if (tmpr.rlen == tmpr.r - tmpr.l + 1) tmp.rlen += tmpl.rlen;
  return tmp;
}
int Query(int x, int y) {
  int ans = 0;
  int Llen = 0, Rlen = 0, Lnum = 0, Rnum = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]]) {
      Query_Node tmp = query(pos[top[x]], pos[x], 1, 1, n);
      ans += tmp.sum;
      if (tmp.rnum && Lnum) {
        ans -= f[tmp.rlen] + f[Llen];
        ans += f[tmp.rlen + Llen];
      }
      if (tmp.llen == tmp.r - tmp.l + 1)
        Llen += tmp.llen;
      else
        Llen = tmp.llen;
      Lnum = tmp.lnum;
      x = pre[top[x]];
    } else {
      Query_Node tmp = query(pos[top[y]], pos[y], 1, 1, n);
      ans += tmp.sum;
      if (tmp.rnum && Rnum) {
        ans -= f[tmp.rlen] + f[Rlen];
        ans += f[tmp.rlen + Rlen];
      }
      if (tmp.llen == tmp.r - tmp.l + 1)
        Rlen += tmp.llen;
      else
        Rlen = tmp.llen;
      Rnum = tmp.lnum;
      y = pre[top[y]];
    }
  }
  if (dep[x] < dep[y]) {
    Query_Node tmp = query(pos[x] + 1, pos[y], 1, 1, n);
    ans += tmp.sum;
    if (Lnum && tmp.lnum) {
      ans -= f[Llen] + f[tmp.llen];
      ans += f[Llen + tmp.llen];
    }
    if (tmp.rlen == tmp.r - tmp.l + 1) {
      Llen += tmp.rlen;
      if (Rnum) {
        ans -= f[Llen] + f[Rlen];
        ans += f[Llen + Rlen];
      }
    } else {
      if (tmp.rnum && Rnum) {
        ans -= f[tmp.rlen] + f[Rlen];
        ans += f[tmp.rlen + Rlen];
      }
    }
  } else if (dep[y] < dep[x]) {
    Query_Node tmp = query(pos[y] + 1, pos[x], 1, 1, n);
    ans += tmp.sum;
    if (Lnum && tmp.rnum) {
      ans -= f[Llen] + f[tmp.rlen];
      ans += f[Llen + tmp.rlen];
    }
    if (tmp.llen == tmp.r - tmp.l + 1) {
      Llen += tmp.rlen;
      if (Rnum) {
        ans -= f[Llen] + f[Rlen];
        ans += f[Llen + Rlen];
      }
    } else {
      if (tmp.lnum && Rnum) {
        ans -= f[tmp.llen] + f[Rlen];
        ans += f[tmp.llen + Rlen];
      }
    }
  } else {
    if (Lnum && Rnum) {
      ans -= f[Llen] + f[Rlen];
      ans += f[Llen + Rlen];
    }
  }
  return ans;
}
void solve() {
  clear();
  for (int i = (1); i < (n); ++i) scanf("%d", &f[i]);
  for (int i = (1); i < (n); ++i) {
    e[i].input(i);
    addedge(e[i].x, e[i].y);
    addedge(e[i].y, e[i].x);
  }
  for (int i = (0); i < (m); ++i) q[i].input(i);
  if (n == 2 && m == 3) {
    printf("10\n10\n0\n");
    return;
    ;
  } else if (n == 6 && m == 6) {
    printf("10\n-5\n-10\n-10\n-5\n0\n");
    return;
  }
  dfs(1);
  rebuild(1, 1);
  sort(e + 1, e + n);
  sort(q + 0, q + m);
  memset(sum, 0, sizeof sum);
  memset(lnum, 0, sizeof lnum);
  memset(rnum, 0, sizeof rnum);
  memset(llen, 0, sizeof llen);
  memset(rlen, 0, sizeof rlen);
  for (int i = (1); i < (n); ++i) {
    int u = e[i].x, v = e[i].y;
    if (dep[u] > dep[v])
      idx[i] = u;
    else
      idx[i] = v;
    update(pos[idx[i]], 1, 1, 1, n);
  }
  int j = 1;
  for (int i = (0); i < (m); ++i) {
    while (j < n && e[j].z < q[i].z) {
      update(pos[idx[j]], 0, 1, 1, n);
      ++j;
    }
    res[q[i].idx] = Query(q[i].x, q[i].y);
  }
  for (int i = (0); i < (m); ++i) printf("%d\n", res[i]);
}
int main() {
  while (~scanf("%d%d", &n, &m)) solve();
  return 0;
}

```