问题描述

动态王国中有 $N$ 个村庄，编号从 $0$ 到 $N-1$。这些村庄通过 $M$ 条道路相互连接。"相互连接" 意味着从任意一个村庄出发，可以经过一些道路到达任意另一个村庄。某一天，由于一次大规模的灾害，所有道路都被破坏了，无法再进行村庄之间的移动。你接到了国王高桥君的委托，需要修复道路，使得动态王国的 $N$ 个村庄重新相互连接。

你首先估计了修复每条道路所需的费用和时间。然后，决定计算在选择适当的道路进行修复时，能够实现“成本最低的最小时薪”的最小值。“成本最低的最小时薪”指的是使得“总修复时间 × 时薪”等于“总修复费用”的时薪的最小值。

请注意，并不一定需要修复所有的道路，也可以修复一些不必要连接村庄的道路。

输入

输入以以下格式从标准输入中给出。

$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$

• 第 $1$ 行包含两个整数，分别表示村庄的个数 $N (2 ≦ N ≦ 10^4)$ 和道路的数量 $M (1 ≦ M ≦ 10^4)$。
• 接下来的 $M$ 行描述道路信息。其中第 $i$ 行包含 $4$ 个整数 $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)$，表示存在一条连接村庄 $A_i$ 和村庄 $B_i$ 的道路，修复该道路需要费用 $C_i$ 和时间 $T_i$。
• 此外，以下条件在道路信息中成立：
  • 对于所有 $i$，$A_i \neq B_i$。
  • 对于所有 $i, j (i \neq j)$，"($A_i \neq A_j$ 或 $B_i \neq B_j$) 且 ($A_i \neq B_j$ 或 $B_i \neq A_j$)"。

部分得分

此问题设置了部分得分。

• 对于满足 $M \leq 16$ 的所有测试用例，如果答案正确，将给予 $20$ 分。

输出

请输出满足条件的“成本最低的最小时薪”的最小值。

输出应为一行。

输入示例1

3 2
0 1 5 3
1 2 5 2

输出示例1

2

在此示例中，为了使村庄相互连接，需要修复所有的道路。由于修复所有道路的总费用为 $10$，总时间为 $5$，因此实现"成本最低的最小时薪"的最小值为 $2$。

由于允许绝对误差 $10^{-2}$，所以输出 $2.01$ 或 $1.99$ 等都是正确的。

输入示例2

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

输出示例2

1.500

在此示例中，当修复第一条道路和第三条道路时，"成本最低的最小时薪"为 $1.5$，这是最小值。

输入示例3

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

输出示例3

1.3333333

在此示例中，修复所有的道路时，"成本最低的最小时薪"为 $1.333...$，这是最小值。