# Start of the new journey

# 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 ofcars / 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** ) and

^{3}

**M**(

**1**≤

**M**≤

**) are given in the first line. Each of next**

`10`^{4}

**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}

**), and the width of the road**

`10`^{3}

**(**

`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..**

3 2 2 1 2 4 2 3 5 3

428571