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.

$\text{[math]}$

Tavas' favorite strings are binary strings (they contain only 0 and 1). For any binary string like s = s₁s₂... s_k, 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 x₁, x₂, ..., x_m.

Define $\text{[math]}$ 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: e₁, e₂, ..., e_x.

Build the binary string b of length x such that: b_i = 1 if and only if l ≤ w(e_i) 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 ≤ 10⁵ and 1 ≤ q ≤ 10⁵).

The next line contains n - 1 space separated integers f₁, f₂, ..., f_n - 1 (|f_i| ≤ 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 ≤ 10⁹).

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 ≤ 10⁹).

Output

Print the answer of each query in a single line.

Tavas on the Path

Examples