#include <bits/stdc++.h>
using namespace std;
int i, j, k, n, m;
int h[200010];
struct wen {
  int x, y, z, id;
} c[200010];
struct ww {
  int a, l, ll, s, k_you, sl, sr, ge, cov;
};
struct lct {
  int n, t;
  ww a[200010];
  vector<int> b[200010];
  int quan[200010], id[200010], an[200010], g[200010];
  void update(int x) {
    if (!x) return;
    int y = a[x].l, z = a[x].ll;
    int f = x <= n ? 1 : a[x].k_you, s = x <= n ? 0 : a[x].k_you;
    a[x].ge = a[y].ge + a[z].ge + (x > n);
    if (!f) {
      a[x].sl = a[y].sl;
      a[x].sr = a[z].sr;
      a[x].s = a[y].s + a[z].s;
    } else {
      a[x].sl = a[y].ge == a[y].sl ? a[y].sl + s + a[z].sl : a[y].sl;
      a[x].sr = a[z].ge == a[z].sr ? a[z].sr + s + a[y].sr : a[z].sr;
      a[x].s =
          a[y].s + a[z].s - h[a[y].sr] - h[a[z].sl] + h[a[y].sr + s + a[z].sl];
    }
  }
  void right(int x) {
    int y = a[x].a, z = a[y].a;
    if (a[z].l == y) a[z].l = x;
    if (a[z].ll == y) a[z].ll = x;
    a[x].a = z, a[y].a = x;
    a[y].l = a[x].ll;
    a[x].ll = a[a[y].l].a = y;
    update(y);
  }
  void left(int x) {
    int y = a[x].a, z = a[y].a;
    if (a[z].l == y) a[z].l = x;
    if (a[z].ll == y) a[z].ll = x;
    a[x].a = z, a[y].a = x;
    a[y].ll = a[x].l;
    a[x].l = a[a[y].ll].a = y;
    update(y);
  }
  bool isroot(int x) {
    return !a[x].a || a[a[x].a].l != x && a[a[x].a].ll != x;
  }
  void fan(int x) {
    if (!x) return;
    swap(a[x].l, a[x].ll);
    a[x].cov ^= 1;
    swap(a[x].sl, a[x].sr);
  }
  void renew(int x) {
    if (!x) return;
    if (a[x].cov) fan(a[x].l), fan(a[x].ll);
    a[x].cov = 0;
  }
  void splay(int x) {
    int y, z;
    for (y = g[z = 1] = x; !isroot(y); g[++z] = a[y].a, y = a[y].a)
      ;
    for (; z; z--) renew(g[z]);
    for (; !isroot(x);) {
      y = a[x].a, z = a[y].a;
      if (isroot(y))
        if (a[y].l == x)
          right(x);
        else
          left(x);
      else if (a[z].l == y)
        if (a[y].l == x)
          right(y), right(x);
        else
          left(x), right(x);
      else if (a[y].l == x)
        right(x), left(x);
      else
        left(y), left(x);
    }
    update(x);
  }
  int access(int x) {
    int y = 0;
    for (; x; y = x, x = a[x].a) {
      splay(x);
      a[x].ll = y;
      update(x);
    }
    return y;
  }
  void ti(int x) {
    access(x);
    splay(x);
    fan(x);
  }
  void add(int x, int y) {
    b[x].push_back(y);
    b[y].push_back(x);
  }
  void dfs(int x, int y) {
    int i;
    for (i = 0; i < b[x].size(); i++) {
      int A = b[x][i];
      if (A == y) continue;
      a[A].a = x;
      update(A);
      dfs(A, x);
    }
  }
  void into(int nn) {
    n = nn;
    t = n;
    int i;
    for (i = 1; i <= n - 1; i++) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      add(x, ++t);
      add(t, y);
      quan[t] = z;
    }
    dfs(1, 0);
  }
  void cal(int x, int y, int id) {
    ti(x);
    access(y);
    splay(y);
    an[id] = a[y].s;
  }
  void work() {
    int i, j;
    for (i = 1; i <= t; i++) id[i] = i;
    sort(id + 1, id + t + 1, [&](int A, int B) { return quan[A] > quan[B]; });
    j = 1;
    for (i = 1; i <= m; i++) {
      int zhi = c[i].z;
      for (; j <= t && quan[id[j]] >= zhi; j++) {
        int A = id[j];
        access(A);
        splay(A);
        a[A].k_you = 1;
        update(A);
      }
      cal(c[i].x, c[i].y, c[i].id);
    }
    for (i = 1; i <= m; i++) printf("%d\n", an[i]);
  }
} a;
inline bool cc1(const wen &a, const wen &b) { return a.z > b.z; }
int main() {
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n - 1; i++) scanf("%d", &h[i]);
  a.into(n);
  for (i = 1; i <= m; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    c[i] = (wen){x, y, z, i};
  }
  sort(c + 1, c + m + 1, cc1);
  a.work();
  return 0;
}

### Prompt

Your task is to create 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;
int i, j, k, n, m;
int h[200010];
struct wen {
  int x, y, z, id;
} c[200010];
struct ww {
  int a, l, ll, s, k_you, sl, sr, ge, cov;
};
struct lct {
  int n, t;
  ww a[200010];
  vector<int> b[200010];
  int quan[200010], id[200010], an[200010], g[200010];
  void update(int x) {
    if (!x) return;
    int y = a[x].l, z = a[x].ll;
    int f = x <= n ? 1 : a[x].k_you, s = x <= n ? 0 : a[x].k_you;
    a[x].ge = a[y].ge + a[z].ge + (x > n);
    if (!f) {
      a[x].sl = a[y].sl;
      a[x].sr = a[z].sr;
      a[x].s = a[y].s + a[z].s;
    } else {
      a[x].sl = a[y].ge == a[y].sl ? a[y].sl + s + a[z].sl : a[y].sl;
      a[x].sr = a[z].ge == a[z].sr ? a[z].sr + s + a[y].sr : a[z].sr;
      a[x].s =
          a[y].s + a[z].s - h[a[y].sr] - h[a[z].sl] + h[a[y].sr + s + a[z].sl];
    }
  }
  void right(int x) {
    int y = a[x].a, z = a[y].a;
    if (a[z].l == y) a[z].l = x;
    if (a[z].ll == y) a[z].ll = x;
    a[x].a = z, a[y].a = x;
    a[y].l = a[x].ll;
    a[x].ll = a[a[y].l].a = y;
    update(y);
  }
  void left(int x) {
    int y = a[x].a, z = a[y].a;
    if (a[z].l == y) a[z].l = x;
    if (a[z].ll == y) a[z].ll = x;
    a[x].a = z, a[y].a = x;
    a[y].ll = a[x].l;
    a[x].l = a[a[y].ll].a = y;
    update(y);
  }
  bool isroot(int x) {
    return !a[x].a || a[a[x].a].l != x && a[a[x].a].ll != x;
  }
  void fan(int x) {
    if (!x) return;
    swap(a[x].l, a[x].ll);
    a[x].cov ^= 1;
    swap(a[x].sl, a[x].sr);
  }
  void renew(int x) {
    if (!x) return;
    if (a[x].cov) fan(a[x].l), fan(a[x].ll);
    a[x].cov = 0;
  }
  void splay(int x) {
    int y, z;
    for (y = g[z = 1] = x; !isroot(y); g[++z] = a[y].a, y = a[y].a)
      ;
    for (; z; z--) renew(g[z]);
    for (; !isroot(x);) {
      y = a[x].a, z = a[y].a;
      if (isroot(y))
        if (a[y].l == x)
          right(x);
        else
          left(x);
      else if (a[z].l == y)
        if (a[y].l == x)
          right(y), right(x);
        else
          left(x), right(x);
      else if (a[y].l == x)
        right(x), left(x);
      else
        left(y), left(x);
    }
    update(x);
  }
  int access(int x) {
    int y = 0;
    for (; x; y = x, x = a[x].a) {
      splay(x);
      a[x].ll = y;
      update(x);
    }
    return y;
  }
  void ti(int x) {
    access(x);
    splay(x);
    fan(x);
  }
  void add(int x, int y) {
    b[x].push_back(y);
    b[y].push_back(x);
  }
  void dfs(int x, int y) {
    int i;
    for (i = 0; i < b[x].size(); i++) {
      int A = b[x][i];
      if (A == y) continue;
      a[A].a = x;
      update(A);
      dfs(A, x);
    }
  }
  void into(int nn) {
    n = nn;
    t = n;
    int i;
    for (i = 1; i <= n - 1; i++) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      add(x, ++t);
      add(t, y);
      quan[t] = z;
    }
    dfs(1, 0);
  }
  void cal(int x, int y, int id) {
    ti(x);
    access(y);
    splay(y);
    an[id] = a[y].s;
  }
  void work() {
    int i, j;
    for (i = 1; i <= t; i++) id[i] = i;
    sort(id + 1, id + t + 1, [&](int A, int B) { return quan[A] > quan[B]; });
    j = 1;
    for (i = 1; i <= m; i++) {
      int zhi = c[i].z;
      for (; j <= t && quan[id[j]] >= zhi; j++) {
        int A = id[j];
        access(A);
        splay(A);
        a[A].k_you = 1;
        update(A);
      }
      cal(c[i].x, c[i].y, c[i].id);
    }
    for (i = 1; i <= m; i++) printf("%d\n", an[i]);
  }
} a;
inline bool cc1(const wen &a, const wen &b) { return a.z > b.z; }
int main() {
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n - 1; i++) scanf("%d", &h[i]);
  a.into(n);
  for (i = 1; i <= m; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    c[i] = (wen){x, y, z, i};
  }
  sort(c + 1, c + m + 1, cc1);
  a.work();
  return 0;
}

```