MINIEYE has n factories around the world and each factory will manufacture different product models according to the manufacture plan. Factory i plans to begin production at day li and end at day ri, including the begin and the end day, so total production time is (ri-li+1) days. The factory needs to bring in ki devices before the lith day to begin production.
The devices can be purchased locally or borrowed and transported from other factories. The price of the devices varies in different regions.
Each device will cost ai RMB if factory i purchases it locally.
If factory i plans to borrow some devices from another MINIEYE factory, say factory i wants to borrow x devices from factory j, first, factory j must have completed all the manufacture tasks, so rj < li, because devices must be ready before lith day; second, there must be a route between factory i and factory j, and all the routes will be given in the input; finally, factory i needs to pay x × dis(i, j) RMB for the transportation. Note that, factory i can only purchase or borrow devices before day li, and once it has ki devices it cannot purchase or borrow any more.
M is responsible for manufacturing, and he needs your help to figure out the minimum cost of money to complete all manufacture tasks on time as scheduled.
The first line contains two integers n, m(1 ≤ n ≤ 50).
For the following n lines, the ith line contains four integers l, r, k, a(1 ≤ li < ri ≤ 107, 1 ≤ ki, ai ≤ 107).
For the following m lines, the ith line contains two integers ui, vi, wi(1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 107), describing an undirected edge between ui and vi with cost wi per device.
Output the minimum cost in a single line.