题目描述

一个通信网络有 $N$ 个结点和 $M$ 条双向光纤。第 $i$ 条光纤连接结点 $U_i$ 和 $V_i$，铺设成本为 $F_i$，带宽为 $S_i$。

一条从结点 $1$ 到结点 $N$ 的路径，其成本为路径上所有光纤成本之和，其带宽为路径上所有光纤带宽的最小值。

请选择一条路径，使路径带宽与路径成本的比值最大，并输出这个最大比值乘以 $10^6$ 后向下取整的结果。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，每行包含四个整数 $U_i,V_i,F_i,S_i$，表示一条双向光纤。

输出格式

输出一个整数，表示所求最大比值乘以 $10^6$ 后向下取整的结果。

样例

3 2
2 1 5 6
2 3 9 3

214285

数据范围与提示

• $2 \le N \le 1000$
• $1 \le M \le 1000$
• $1 \le U_i,V_i \le N$，且 $U_i \ne V_i$
• $1 \le F_i,S_i \le 1000$
• 保证结点 $1$ 可以到达结点 $N$