### 问题描述 小齐最近购置了一个新的农场，想要将农场产的牛奶输送到附近的城镇。农场和城镇之间通过一系列管道相连，小齐想要找到一组最佳的管道，以便将牛奶从农场输送到城镇。 管道网络由 $N$ 个连接点（管道的端点）描述，方便地编号为 $1 \ldots N$。连接点 $1$ 表示小齐的农场，连接点 $N$ 表示城镇。有 $M$ 条双向管道，每条管道连接一对连接点。第 $i$ 条管道购置费用为 $c_i$ 美元，可以支持每秒 $f_i$ 升的牛奶流动。 小齐想要购置一条管道路径，该路径的端点为连接点 $1$ 和 $N$。路径的费用是路径上所有管道费用的总和。路径上的流速是路径上所有管道流速的最小值（因为这是流向路径的瓶颈）。小齐希望最大化路径的流速与路径费用的比值。保证存在一条从 $1$ 到 $N$ 的路径。 ### 输入格式 第一行输入 $N$ 和 $M$。 接下来的 $M$ 行描述了每条管道，每行包含四个整数：$a$ 和 $b$（由管道连接的两个不同连接点），$c$（管道的费用），$f$（管道的流速）。费用和流速都是 $1 \leq x \leq 1000$ 的正整数。 ### 输出格式 请输出 $10^6$ 倍的最优解值，取整数部分。 ### 样例输入 ``` 3 2 2 1 2 4 2 3 5 3 ``` ### 样例输出 ``` 428571 ``` ### 评测数据规模 $2 \leq N \leq 1000$，$1 \leq M \leq 1000$。