Milk Pumping Optimization

Farmer John is expanding his dairy empire by acquiring a new farm that is connected to a nearby town via a network of pipelines. The network is represented as a graph with N junctions (numbered from 1 to N), where junction 1 is the farm and junction N is the town. There are M bidirectional pipelines; each pipeline connects two junctions, has a purchase cost c_i dollars, and can support a flow of f_i liters of milk per second.

When Farmer John purchases a set of pipelines that form a simple path from junction 1 (the farm) to junction N (the town), the total cost of the path is the sum of the costs of all pipelines in the path, and the flow along the path is determined by the minimum flow capacity among those pipelines (i.e. the bottleneck). His objective is to choose a single path that maximizes the ratio

\(\frac{\text{flow}}{\text{cost}}\)

Since the ratio can be a fractional number, you are required to output the value of the maximum ratio multiplied by \(10^6\) (and truncated to an integer).

It is guaranteed that there is at least one valid path from junction 1 to junction N.

inputFormat

The first line contains two integers N and M, representing the number of junctions and pipelines respectively.

Each of the next M lines contains four integers u, v, c, and f, which describe a bidirectional pipeline connecting junctions u and v with cost c and milk flow capacity f.

outputFormat

Output a single integer, the maximum achievable \(\frac{\text{flow}}{\text{cost}}\) multiplied by \(10^6\), truncated to an integer.

sample

3 3
1 2 3 4
2 3 2 3
1 3 5 2

600000