市长想在成立里面建造一个天然气网络，这个管道网络可以用 N 个点（管道的端点）来表示，编号为
1…N。1 号点表示天然气网络的输入点，点 N 表示天然气网络的输出点。有 M 条双向的管道，每条连接了两个点。使用第 i 条管道需要花费$c_i$元购入，可以支持每秒$f_i$升的流量。

市长想要购买一条管道组成一条单一路径，路径的两端分别为点 1 和 N。这条路径的花费等于路径上所有管道的费用之和。路径上的流量等于路径上所有管道的最小流量。市长想要最大化路径流量与路径花费之比。数据保证存在从 1 到 N之间的路径。

第一行两个整数 N 和 M。

接下来 M 行每行以四个整数描述一条管道：a 和 b（管道连接的两个端点，保证不同），c（使用管道的花费），以及 f（管道的流量）。花费和流量均为范围$1\dots 1000$之内的正整数。

输出最优解的值乘以$10^6$后向下取整的值。

$2\leq N \leq 1000, 1\leq M,c,f \leq 1000,$