当前没有测试数据。

题目描述

某城市的网络由 $N$ 个结点和 $M$ 条光纤组成，每条光纤连接两个不同的结点用于这两个结点双向传递信息。

每条光纤有如下两个属性：

• 成本：$F_i$，表示铺设该光纤的费用。
• 带宽：$S_i$，表示该光纤支持的数据传输速率。

现需要选择一条从编号为 $1$ 的结点到编号为 $N$ 的结点的路径，使得路径的带宽与成本的比值最大化。

对于一条从编号为 $1$ 的结点出发到编号为 $N$ 的结点结束的路径，该路径的带宽和成本的定义如下：

• 路径成本：路径上所有光纤的成本之和。
• 路径带宽：路径上所有光纤的最小带宽。

请编程计算出从编号为 $1$ 的结点出发，到编号为 $N$ 的结点结束，最优路径的带宽与成本的比值，并将结果乘以 $10^6$ 后向下取整输出。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$，分别表示结点数量和光纤数量。

接下来的 $M$ 行，每行包含四个整数 $U_i$、$V_i$、$F_i$ 和 $S_i$，表示一条连接节点 $U_i$ 和 $V_i$ 的光纤，其成本为 $F_i$，带宽为 $S_i$。

输出格式

输出一个整数，表示最优路径的带宽与成本之比乘以 $10^6$ 后向下取整的结果。

样例 #1

输入

3 2
2 1 5 6
2 3 9 3

输出

214285

数据范围

对于 $10\%$ 的数据，满足图为链形，也就是说每个结点最多只有 $2$ 条与其连接的光纤。

对于 $40\%$ 的数据，满足 $1 \le N, M \le 100$。

对于 $100\%$ 的数据，满足 $2 \le N \le 1000$，$1 \le M \le 1000$，$1 \le F_i, S_i \le 1000$，$1 \le U_i, V_i \le N$，$U_i \neq V_i$。