Start of the new journey
The day came, ladies and gentlemen! We are taking the bride! However, as always, we are left with narrow roads of Baku and kids block the way of the cars and want some money traditionally. The poor guy Rashad is, has no much money to spend on kids! Also, he wants as much as cars going alongside with him. He thought a lot and decided to choose a path with maximum effectiveness. The effectiveness of the path is defined by the maximum number of cars he can take divided by the total cost he needs to give to children (effectiveness = number_of_cars / total_cost). When starting a path, the number of cars Rashad can take is equal to the minimum width of all roads in the path. We are given the available roads of Baku, with each road having its width and cost and connecting two locations,and you need to find the maximum effectiveness of the possible path going from location 1 to location N. See the output format for output details.
Input
The numbers N (1 ≤ N ≤ 10^3 ) and M (1 ≤ M ≤ 10^4 ) are given inthe first line. Each of next M lines contain 4 numbers, the first endpoint of the road,the second endpoint of the road, the cost of the road x[i] (1 ≤ x[i] ≤ 10^3 ), and the width of the road y[i] (1 ≤ y[i] ≤ 10^3 ).
Output
Print the 1000000 times the maximum effectiveness of the road,rounded down to the nearest integer.
Explanation for first test case
In this example, there is only one path from 1 to N. The width is min(3, 4)=3 and the cost is 2+5=7. 3/7=0.428571428571..