L. Los Ratones III
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

In the distant hills, there was the city of Ratonia, home of the Ratones. Its streets were connected in a very special way: between any two houses, there was exactly one unique path.

Each house in Ratonia had a unique identifier (from 1 to N). Additionally, every street connecting two houses had its own value (from 1 to 1000000000).

After returning from a tournament, the Ratones received Q letters from their fans.

In every letter, the fans asked the same request:

"Dear Ratones, could you tell us the sum of all edge values along the path that connects the house with identifier u and the house with identifier v after multiplying the hole path by x?"

Since the Ratones don't know how to answer these requests themselves, they have asked for your help.

Input

The first line of input contains two integers $$$N$$$ and $$$Q$$$ $$$(1 \leq N, Q \leq 100000)$$$, the number of houses and the number of letters.

The next $$$N-1$$$ lines contains tree integers $$$u$$$ $$$v$$$ $$$c$$$ $$$(1 \leq u,v \leq N)$$$ $$$(u!=v)$$$ $$$(1 \leq c \leq 1000000000)$$$, this means that the there exists a path between u and v with value c

The next $$$Q$$$ lines contains two integers $$$u$$$ $$$v$$$ $$$x$$$ $$$(1 \leq u,v \leq N)$$$ $$$(1 \leq x \leq 1000000000)$$$, the question that the fans asked

Output

For each letter respond to the request. Since the answer may be very large, output it modulo $$$1000000007$$$.

Example
Input
5 3
1 2 1
2 3 1
3 4 1
4 5 1
1 2 2
1 5 1
1 5 2
Output
2
5
10
Note

Each query is persistent. This means that after processing a query (u, v, x), every edge on the path between u and v is multiplied by x permanently. Subsequent queries must be answered considering all the modifications applied by the previous ones.