### 问题描述 小齐购买了一辆新车，但在选购额外功能时，不小心点击了两次“提交”按钮，导致车辆上装有两个 $GPS$ 导航系统。更糟糕的是，这两个系统经常在农夫 $John$ 该选择的路线上作出相互冲突的决策。 该地区的地图由 $N$个交叉口和 $M$ 条单向道路组成。第 $i$ 条道路连接交叉口 $A_i$ 和 $B_i$。同一对交叉口可能有多条道路连接，而双向道路（允许双向行驶）则由两条相反方向的单向道路表示。$John$ 的家位于交叉口 $1$，农场位于交叉口 $N$。可以通过沿着一系列方向道路从他的家到达农场。 两个 $GPS$ 单位使用与上述相同的基本地图，但它们对每条道路的行驶时间有不同的理解。根据第一个 $GPS$ 单位，道路 $i$ 消耗 $P_i$ 单位的时间，而根据第二个 $GPS$ 单位，道路 $i$ 消耗 $Q_i$ 单位的时间（每个行驶时间在 $1$ 到 $100,000$ 的范围内为整数）。 小齐想从家到农场出行。然而，每当小齐选择的路线使得 $GPS$ 单位认为某条道路不属于从 $X$ 到农场的最短路径时，$GPS$ 单位就会大声抱怨（甚至可能两个 $GPS$ 单位都抱怨，如果小齐选择了两个 $GPS$ 都不喜欢的道路）。 请帮助小齐确定如果他适当选择他的路径，他可能收到的最小投诉总数。如果两个 $GPS$ 单位在小齐选择某条道路时都抱怨，这将计为总数的 $+2$。 ### 输入格式 第 $1$ 行：两个以空格分隔的整数 $N$ 和 $M$。 接下来 $N$ 行：第 $i$ 行包含四个整数：$A_i$、$B_i$、$P_i$ 和 $Q_i$。 ### 输出格式 如果小齐从他的家到农场的路径最优，则他可能收到的最小投诉总数。 ### 样例输入 ``` 5 7 3 4 7 1 1 3 2 20 1 4 17 18 4 5 25 3 1 2 10 1 3 5 4 14 2 4 6 5 ``` ### 样例输出 ``` 1 ``` ### 评测数据规模 $1 \leq N \leq 20,000$，$1 \leq M \leq 50,000$，$1 \leq A_i \leq N$，$1 \leq B_i \leq N$，$1 \leq P_i, Q_i \leq 100,000$。