题目描述

银河联邦在若干颗行星之间建设了一套能源运输网络。现在，指挥官需要从自己的基地行星向首都行星稳定输送能量，于是需要从现有网络中选择一条合适的通道路线。

整个网络由 $N$ 个空间中转站组成，编号为 $1 \sim N$。其中：

• 编号 $1$ 的中转站表示基地行星；
• 编号 $N$ 的中转站表示首都行星。

网络中共有 $M$ 条双向能源通道。第 $i$ 条通道连接两个中转站，建设这条通道需要花费 $c_i$ 单位资源，并且它每秒最多可传输 $f_i$ 单位能量。

现在，指挥官希望选择一条从 $1$ 到 $N$ 的简单路径作为运输路线。

定义这条路线的：

• 总代价 为路径上所有通道建设费用之和；
• 有效传输率 为路径上所有通道传输能力的最小值。

为了提高资源利用效率，指挥官希望最大化：

$$\frac{\text{有效传输率}}{\text{总代价}}$$

已知一定存在至少一条从 $1$ 到 $N$ 的路径。

---

输入格式

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

接下来 $M$ 行，每行四个整数 $a,b,c,f$，表示一条双向能源通道：

• 它连接中转站 $a$ 和 $b$；
• 建设代价为 $c$；
• 最大传输率为 $f$。

其中 $c,f$ 均为 $1 \sim 1000$ 之间的正整数。

---

输出格式

输出

$$\left\lfloor 10^6 \times \frac{\text{最优有效传输率}}{\text{最优路径总代价}} \right\rfloor$$

即将最优比值乘以 $10^6$ 后向下取整输出。

---

输入输出样例 #1

输入 #1

3 2
2 1 2 4
2 3 5 3

输出 #1

428571

---

说明/提示

在这个例子中，从基地行星到首都行星只有一条路线可选。

这条路线的有效传输率为：

$$\min(4,3)=3$$

总代价为：

$$2+5=7$$

因此答案为：

$$\left\lfloor 10^6 \times \frac{3}{7} \right\rfloor = 428571$$

---

数据范围

测试点 $2 \sim 5$ 满足：

$$N,M \le 100$$

对于全部数据：

$$2 \le N \le 1000,\quad 1 \le M \le 1000$$