Problem Description

In the Dynamic Kingdom, there are $ N $ villages numbered from $ 0 $ to $ N-1 $. These villages were connected by $ M $ roads, forming a connected network. Being "connected" means that it is possible to travel from any village to any other village by traversing some roads. One day, a large-scale disaster destroyed all the roads, making it impossible to travel between villages. You have been tasked by King Takahashi to repair the roads and restore the connectivity of the $ N $ villages in the Dynamic Kingdom.

First, you estimated the necessary costs and times to repair each road. Then, you decided to calculate the minimum "minimum wage that makes the repair profitable" when choosing the roads to repair appropriately. The "minimum wage that makes the repair profitable" refers to the wage rate where the total time spent repairing the roads multiplied by the wage equals the total cost of repairing the roads.

Note that it is not necessary to repair all roads, and it is acceptable to repair roads that are not necessary for connecting the villages.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ T_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ T_2 $ : $ A_M $ $ B_M $ $ C_M $ $ T_M $

• The first line contains two integers $N\ (2\ ≦\ N\ ≦\ 10^4)$ representing the number of villages, and $M\ (1\ ≦\ M\ ≦\ 10^4)$ representing the number of roads, separated by spaces.
• The following $ M $ lines contain information about the roads. The $ i $-th line contains four integers $A_i\ (0\ ≦\ A_i\ ≦\ N-1),\ B_i\ (0\ ≦\ B_i\ ≦\ N-1),\ C_i\ (1\ ≦\ C_i\ ≦\ 10^6),\ T_i\ (1\ ≦\ T_i\ ≦\ 10^6)$ separated by spaces, indicating that there is a road connecting village $ A_i $ and village $ B_i $, and the cost to repair this road is $ C_i $, with a time requirement of $ T_i $.

Additionally, the following conditions hold for the road information:

• For all $ i $, $A_i\ \neq\ B_i$
• For all $i,\ j\ (i\ \neq\ j)$, either $A_i\ \neq\ A_j$ or $B_i\ \neq\ B_j$, and $A_i\ \neq\ B_j$ or $B_i\ \neq\ A_j$

Output Format

Output the minimum "minimum wage that makes the repair profitable" on a single line.

The output is accepted if the absolute error is within $ 10^{-2} $.

Ensure to include a newline at the end of the output.

Sample Input and Output

Sample Input #1

3 2
0 1 5 3
1 2 5 2

Sample Output #1

2

Sample Input #2

3 3
0 1 1 1
1 2 3 1
2 0 2 1

Sample Output #2

1.500

Sample Input #3

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

Sample Output #3

1.3333333

Notes/Hints

Partial Points

This problem has partial points.

• If you correctly solve all test cases where $M\ ≦\ 16$, you will be awarded $ 20 $ points.

Sample Explanation 1

In this case, all roads must be repaired to connect the towns. The total cost of repairing all roads is $ 10 $ and the total time is $ 5 $, so the minimum wage that makes the repair profitable is $ 2 $. Outputs like $ 2.01 $ or $ 1.99 $ are also considered correct due to the allowed error of $ 10^{-2} $.

Sample Explanation 2

In this case, repairing the first and third roads results in the minimum "minimum wage that makes the repair profitable", which is $ 1.5 $.

Sample Explanation 3

In this case, repairing all roads results in the minimum "minimum wage that makes the repair profitable", which is $ 1.333... $.

见题面 Input 部分

见题面 Output 部分