某城市的网络由 N 个结点和 M 条光纤组成，每条光纤连接两个不同的结点用于这两个结点双向传递信息。
每条光纤有如下两个属性：
现需要选择一条从编号为 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 后向下取整的结果。
3 2 2 1 5 6 2 3 9 3
214285
4 4 1 2 5 8 2 4 8 9 1 3 9 4 3 4 2 9
615384
10 20 1 6 334 478 4 8 835 429 4 3 686 592 2 1 683 586 5 4 721 862 9 8 268 267 6 2 225 384 4 2 854 499 3 2 215 693 9 3 369 667 6 5 890 259 9 7 778 688 6 7 626 640 1 7 568 639 2 7 142 329 9 10 882 830 8 7 372 636 3 6 214 667 2 10 784 237 2 8 602 617
286804
唯一的路径为 1 \rightarrow 2 \rightarrow 3：
对于 10\% 的数据，满足图为链形，也就是说每个结点最多只有 2 条与其连接的光纤。
对于 40\% 的数据，满足 1 \le N, M \leq 100。
对于 100\% 的数据，满足 2 \leq N \leq 1000，1 \leq M \leq 1000，1 \leq F_i, S_i \leq 1000，1 \le U_i, V_i \le N，U_i \neq V_i。