#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
struct node {
  int top;
  int deep;
  int fa;
  int size;
  int son;
  int place;
} tree[MAXN] = {0};
struct line {
  int y;
  int value;
  int next;
} a[MAXN * 2] = {0};
int head[MAXN] = {0};
int f[MAXN] = {0};
int fi[MAXN] = {0};
int v[MAXN] = {0};
struct sg_tree {
  int l;
  int r;
  int t;
  int b;
} st[MAXN * 4] = {0};
struct que {
  int x;
  int y;
  int v;
  int num;
} qq[MAXN] = {0};
int answer[MAXN] = {0};
int p[MAXN] = {0};
int n, m, tot;
void open() {
  freopen("E.in", "r", stdin);
  freopen("E.out", "w", stdout);
}
void close() {
  fclose(stdin);
  fclose(stdout);
}
inline void add(const int &x, const int &y, const int &value) {
  tot++;
  a[tot].y = y;
  a[tot].value = value;
  a[tot].next = head[x];
  head[x] = tot;
}
inline void dfs(const int &p) {
  tree[p].size = 1;
  for (int i = head[p]; i; i = a[i].next)
    if (!tree[a[i].y].deep) {
      tree[a[i].y].deep = tree[p].deep + 1;
      tree[a[i].y].fa = p;
      dfs(a[i].y);
      tree[p].size += tree[a[i].y].size;
      if (tree[a[i].y].size > tree[tree[p].son].size) tree[p].son = a[i].y;
    }
}
inline void HLD(const int &p) {
  tot++;
  tree[p].place = tot;
  if (tree[p].son) {
    tree[tree[p].son].top = tree[p].top;
    HLD(tree[p].son);
  }
  for (int i = head[p]; i; i = a[i].next)
    if (tree[p].fa != a[i].y && tree[p].son != a[i].y) {
      tree[a[i].y].top = a[i].y;
      HLD(a[i].y);
      fi[a[i].y] = tree[a[i].y].place;
      v[a[i].y] = a[i].value;
    } else if (tree[p].son == a[i].y) {
      fi[a[i].y] = tree[a[i].y].place;
      v[a[i].y] = a[i].value;
    }
}
void init() {
  scanf("%d", &n);
  scanf("%d", &m);
  for (int i = 1, END = n - 1; i <= END; i++) scanf("%d", &f[i]);
  int x, y, value;
  for (int i = 2, END = n; i <= END; i++) {
    scanf("%d", &x);
    scanf("%d", &y);
    scanf("%d", &value);
    add(x, y, value);
    add(y, x, value);
  }
  tree[1].deep = 1;
  dfs(1);
  tot = 0;
  tree[1].top = 1;
  HLD(1);
  for (int i = 1, END = m; i <= END; i++) {
    scanf("%d", &qq[i].x);
    scanf("%d", &qq[i].y);
    scanf("%d", &qq[i].v);
    qq[i].num = i;
  }
  for (int i = 2, END = n; i <= END; i++) p[i - 1] = i;
}
inline sg_tree merge(const sg_tree &a, const sg_tree &b) {
  sg_tree c;
  if (a.b)
    c.l = a.l + b.l;
  else
    c.l = a.l;
  if (b.b)
    c.r = a.r + b.r;
  else
    c.r = b.r;
  c.b = a.b & b.b;
  c.t = a.t + b.t;
  if (a.r && b.l) {
    c.t -= f[a.r] + f[b.l] - f[a.r + b.l];
  }
  return c;
}
void insert(int p, int l, int r, const int &aim) {
  if (l == r) {
    st[p].t = f[1];
    st[p].l = 1;
    st[p].r = 1;
    st[p].b = 1;
    return;
  }
  int mid = (l + r) / 2;
  if (aim <= mid)
    insert((p + p), l, mid, aim);
  else
    insert((p + p + 1), mid + 1, r, aim);
  st[p] = merge(st[(p + p)], st[(p + p + 1)]);
}
sg_tree query(int p, int l, int r, int ll, int rr) {
  if (l == ll && r == rr) return st[p];
  int mid = (l + r) / 2;
  if (rr <= mid)
    return query((p + p), l, mid, ll, rr);
  else if (mid < ll)
    return query((p + p + 1), mid + 1, r, ll, rr);
  else
    return merge(query((p + p), l, mid, ll, mid),
                 query((p + p + 1), mid + 1, r, mid + 1, rr));
}
int query(int u, int v) {
  int fu = tree[u].top, fv = tree[v].top;
  sg_tree nu = {0}, nv = {0};
  while (fu != fv) {
    if (tree[fu].deep < tree[fv].deep) {
      swap(fu, fv);
      swap(nu, nv);
      swap(u, v);
    }
    nu = merge(query(1, 1, n, tree[fu].place, tree[u].place), nu);
    u = tree[fu].fa;
    fu = tree[u].top;
  }
  if (u == v) {
    swap(nu.l, nu.r);
    nu = merge(nu, nv);
    return nu.t;
  } else {
    if (tree[u].deep < tree[v].deep) {
      swap(u, v);
      swap(nu, nv);
    }
    nu = merge(query(1, 1, n, tree[tree[v].son].place, tree[u].place), nu);
    swap(nu.l, nu.r);
    nu = merge(nu, nv);
    return nu.t;
  }
}
bool cmpqq(que a, que b) { return a.v > b.v; }
bool cmpp(int a, int b) { return v[a] > v[b]; }
void query() {
  int poi = 1;
  sort(qq + 1, qq + m + 1, cmpqq);
  sort(p + 1, p + n + 1, cmpp);
  for (int i = 1, END = m; i <= END; i++) {
    for (poi; v[p[poi]] >= qq[i].v && poi < n; poi++) {
      insert(1, 1, n, fi[p[poi]]);
    }
    answer[qq[i].num] = query(qq[i].x, qq[i].y);
  }
  for (int i = 1, END = m; i <= END; i++) printf("%d\n", answer[i]);
}
int main() {
  init();
  query();
  close();
  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 MAXN = 1e5 + 5;
struct node {
  int top;
  int deep;
  int fa;
  int size;
  int son;
  int place;
} tree[MAXN] = {0};
struct line {
  int y;
  int value;
  int next;
} a[MAXN * 2] = {0};
int head[MAXN] = {0};
int f[MAXN] = {0};
int fi[MAXN] = {0};
int v[MAXN] = {0};
struct sg_tree {
  int l;
  int r;
  int t;
  int b;
} st[MAXN * 4] = {0};
struct que {
  int x;
  int y;
  int v;
  int num;
} qq[MAXN] = {0};
int answer[MAXN] = {0};
int p[MAXN] = {0};
int n, m, tot;
void open() {
  freopen("E.in", "r", stdin);
  freopen("E.out", "w", stdout);
}
void close() {
  fclose(stdin);
  fclose(stdout);
}
inline void add(const int &x, const int &y, const int &value) {
  tot++;
  a[tot].y = y;
  a[tot].value = value;
  a[tot].next = head[x];
  head[x] = tot;
}
inline void dfs(const int &p) {
  tree[p].size = 1;
  for (int i = head[p]; i; i = a[i].next)
    if (!tree[a[i].y].deep) {
      tree[a[i].y].deep = tree[p].deep + 1;
      tree[a[i].y].fa = p;
      dfs(a[i].y);
      tree[p].size += tree[a[i].y].size;
      if (tree[a[i].y].size > tree[tree[p].son].size) tree[p].son = a[i].y;
    }
}
inline void HLD(const int &p) {
  tot++;
  tree[p].place = tot;
  if (tree[p].son) {
    tree[tree[p].son].top = tree[p].top;
    HLD(tree[p].son);
  }
  for (int i = head[p]; i; i = a[i].next)
    if (tree[p].fa != a[i].y && tree[p].son != a[i].y) {
      tree[a[i].y].top = a[i].y;
      HLD(a[i].y);
      fi[a[i].y] = tree[a[i].y].place;
      v[a[i].y] = a[i].value;
    } else if (tree[p].son == a[i].y) {
      fi[a[i].y] = tree[a[i].y].place;
      v[a[i].y] = a[i].value;
    }
}
void init() {
  scanf("%d", &n);
  scanf("%d", &m);
  for (int i = 1, END = n - 1; i <= END; i++) scanf("%d", &f[i]);
  int x, y, value;
  for (int i = 2, END = n; i <= END; i++) {
    scanf("%d", &x);
    scanf("%d", &y);
    scanf("%d", &value);
    add(x, y, value);
    add(y, x, value);
  }
  tree[1].deep = 1;
  dfs(1);
  tot = 0;
  tree[1].top = 1;
  HLD(1);
  for (int i = 1, END = m; i <= END; i++) {
    scanf("%d", &qq[i].x);
    scanf("%d", &qq[i].y);
    scanf("%d", &qq[i].v);
    qq[i].num = i;
  }
  for (int i = 2, END = n; i <= END; i++) p[i - 1] = i;
}
inline sg_tree merge(const sg_tree &a, const sg_tree &b) {
  sg_tree c;
  if (a.b)
    c.l = a.l + b.l;
  else
    c.l = a.l;
  if (b.b)
    c.r = a.r + b.r;
  else
    c.r = b.r;
  c.b = a.b & b.b;
  c.t = a.t + b.t;
  if (a.r && b.l) {
    c.t -= f[a.r] + f[b.l] - f[a.r + b.l];
  }
  return c;
}
void insert(int p, int l, int r, const int &aim) {
  if (l == r) {
    st[p].t = f[1];
    st[p].l = 1;
    st[p].r = 1;
    st[p].b = 1;
    return;
  }
  int mid = (l + r) / 2;
  if (aim <= mid)
    insert((p + p), l, mid, aim);
  else
    insert((p + p + 1), mid + 1, r, aim);
  st[p] = merge(st[(p + p)], st[(p + p + 1)]);
}
sg_tree query(int p, int l, int r, int ll, int rr) {
  if (l == ll && r == rr) return st[p];
  int mid = (l + r) / 2;
  if (rr <= mid)
    return query((p + p), l, mid, ll, rr);
  else if (mid < ll)
    return query((p + p + 1), mid + 1, r, ll, rr);
  else
    return merge(query((p + p), l, mid, ll, mid),
                 query((p + p + 1), mid + 1, r, mid + 1, rr));
}
int query(int u, int v) {
  int fu = tree[u].top, fv = tree[v].top;
  sg_tree nu = {0}, nv = {0};
  while (fu != fv) {
    if (tree[fu].deep < tree[fv].deep) {
      swap(fu, fv);
      swap(nu, nv);
      swap(u, v);
    }
    nu = merge(query(1, 1, n, tree[fu].place, tree[u].place), nu);
    u = tree[fu].fa;
    fu = tree[u].top;
  }
  if (u == v) {
    swap(nu.l, nu.r);
    nu = merge(nu, nv);
    return nu.t;
  } else {
    if (tree[u].deep < tree[v].deep) {
      swap(u, v);
      swap(nu, nv);
    }
    nu = merge(query(1, 1, n, tree[tree[v].son].place, tree[u].place), nu);
    swap(nu.l, nu.r);
    nu = merge(nu, nv);
    return nu.t;
  }
}
bool cmpqq(que a, que b) { return a.v > b.v; }
bool cmpp(int a, int b) { return v[a] > v[b]; }
void query() {
  int poi = 1;
  sort(qq + 1, qq + m + 1, cmpqq);
  sort(p + 1, p + n + 1, cmpp);
  for (int i = 1, END = m; i <= END; i++) {
    for (poi; v[p[poi]] >= qq[i].v && poi < n; poi++) {
      insert(1, 1, n, fi[p[poi]]);
    }
    answer[qq[i].num] = query(qq[i].x, qq[i].y);
  }
  for (int i = 1, END = m; i <= END; i++) printf("%d\n", answer[i]);
}
int main() {
  init();
  query();
  close();
  return 0;
}

```