P3106 [USACO14OPEN] Dueling GPSs S

农夫约翰最近在网上购买了一辆新车，但由于匆忙，他在选择汽车的额外功能时不小心点击了两次“提交” 按钮，结果车上配备了两个 GPS 导航系统！更糟糕的是，这两个系统经常对约翰应该走的路线做出相互矛盾的决定。 约翰所在地区的地图由 $N$ 个交叉路口 $(2 \le N \le 10,000)$ 和 $M$ 条单向道路 $(1 \le M \le 50,000)$ 组成。道路 $i$ 连接交叉路口 $A_i(1 \le A_i \le N)$ 和 $B_i(1 \le B_i \le N)$。同一对交叉路口之间可能有多条道路连接，双向道路（允许双向通行）由两个相反方向的单向道路表示。约翰的家位于交叉路口 $1$，他的农场位于交叉路口 $N$。可以通过沿着一系列单向道路从他的家到达农场。 两个 GPS 单元使用的是上述相同的基础地图；然而，它们对每条道路的行驶时间有不同的看法。根据第一个 GPS 单元，道路 $i$ 需要 $P_i$ 个时间单位来行驶，而根据第二个单元，道路 $i$ 需要 $Q_i$ 个时间单位来行驶（每个行驶时间是范围在 $1$ 到 $10^5$ 的整数）。 约翰想从家里到农场。然而，每当约翰走一条（比如，从交叉路口 $X$ 到交叉路口 $Y$）GPS 单元认为不是从 $X$ 到农场的最短路线的一部分的道路时， GPS 单元就会大声抱怨（如果约翰走的道路两个 GPS 单元都不喜欢，两个 GPS 单元都会抱怨）。 请帮助约翰确定如果他适当地选择路线，他可以收到的最少总抱怨次数。如果约翰走的道路让两个 GPS 单元都抱怨，这将计为两次抱怨。

第 $1$ 行：整数 $N$ 和 $M$。 接下来 $M$ 行，第 $i+1$ 行描述道路 $i$，有四个整数：$A_i,B_i,P_i,Q_i$。

共一行，如果约翰从家到农场的路线选择最优，他可以收到的最少总抱怨次数。

有 $5$ 个交叉路口和 $7$ 条单向道路。第一条道路从交叉路口 $3$ 连接到交叉路口 $4$；第一个 GPS 认为这条路需要 $7$ 个时间单位来行驶，而第二个 GPS 认为需要 $1$ 个时间单位，等等。 如果约翰走 $1 \to 2 \to 4 \to 5$ 的路径，那么第一个 GPS 会在 $1 \to 2$ 的道路上抱怨（它更喜欢 $1 \to 3$ 的道路）。然而，对于路径的其余部分 $2 \to 4 \to 5$，两个 GPS 都很满意，因为这对于每个 GPS 来说都是从 $2$ 到 $5$ 的最短路径。