You live in a city that contains $N$ houses. Each house is reachable from every other house through a unique path, which implies that there are $N-1$ roads in the city. Each of the $N-1$ road is distinct and has a length denoted by an array $L$. You want to reach directly from house $i$ to house $j$ ($1 \le i,j \le N \ and \ i \ne j$) by traversing not more than $X$ units of road length. To reach directly from a house $i$ to house $j$, you can select exactly one road of length less than or equal to $X$ and destroy that road completely and construct a road between the two houses $i$ and $j$ but the condition is that the every house should be reachable from every other house.

Your task is to solve $Q$ queries (each query is independent from each other ) of the following form:

$A \ B \ X$

where $(A,B)$ denotes the pair of the houses that you want to connect. For each query, determine the number of ways in which you can select an ordered pair of houses $(G,H)$ such that the following condidtions hold:

• There should be a road between the houses $G$ and $H$

• The length of the road between the houses $G$ and $H$ is less than or equal to $X$

• After removing the road between $G$ and $H$ and adding a road between $A$ and $B$ , the houses $G$ and $H$ should still be connected through a path in the city

Input format

• First line: Two space-separated integers $N$ and $Q$ 
• Next $N-1$ lines: Three space-separated integers $U$, $V$, and $L_i$ denoting a bidirectional path from the house $U$ to $V$ and vice versa of length $L_i$
• Next $Q$ lines: Three space-separated integers $A$, $B$, and $X$ 

Output format

For each query, print the answer on a separate line.

Constraints

$2 \le N,Q \le 2*10^5$

$1 \le A, B \le N$ and $A \ne B$

$1 \le L_i , X \le 10^6$

Subtasks

• For 10 points: $2 \le N,Q \le 200$
• For 20 points: $2 \le N,Q \le 2000$
• For 70 points: Original constraints