Wandering Businessman’s Profitable Journey

A country A has n cities numbered from 1 to n connected by n-1 roads forming a tree. Each city i has three associated integers: A_i (the prosperity threshold), B_i (the profit gained if you meet the threshold) and C_i (the cost incurred otherwise).

You are a wandering businessman planning to travel on m trips. For the i-th trip, you will start at city S_i and travel along the unique shortest path to city T_i with an initial capital of X coins. At every city on your way (including both the starting and ending cities) you must perform a trade:

• If your current capital w is not less than the city’s prosperity value A_i, you gain a profit of B_i coins and count this as one profitable trade.
• Otherwise, you lose C_i coins.

After completing the trade at the destination city T_i, you require that your final capital is at least Y_i coins and that you have achieved at least K_i profitable trades along the journey. Note that Y_i may be less than X since bankruptcy is of no concern to you, and detours might offer beautiful scenery.

Your task is to determine the minimum value of X such that if you start every trip with X coins, every trip will end with a capital of at least Y_i coins and with at least K_i profitable trades.

Note: The tree structure guarantees that there is exactly one shortest path between any two cities.

inputFormat

The input consists of multiple lines:

1. The first line contains two integers n and m separated by a space, where n is the number of cities and m is the number of trips.
2. The next n-1 lines each contain two integers u and v indicating that there is a bidirectional road between cities u and v.
3. The following n lines describe the cities. The i-th of these lines contains three integers: A_i, B_i, and C_i.
4. The next m lines each describe a trip. The i-th such line contains four integers: S_i, T_i, Y_i, and K_i, representing the start city, destination city, minimum required final capital, and minimum number of profitable trades, respectively.

outputFormat

Output a single integer — the minimum initial capital X needed so that all m trips satisfy the requirements.

sample

5 3
1 2
2 3
2 4
1 5
10 5 3
20 10 5
15 7 4
5 3 2
8 4 1
1 3 20 2
4 3 10 1
5 4 0 1

16