题目描述

农场主 John 最近在网上买了一辆新车，在购买汽车配件时，John 不小心点了两次“提交”按钮。导致汽车上安装了两套 GPS 系统，更糟糕的是 John 在使用 GPS 导航时，两套系统常常给出不同的路线。从地图上看，John 居住的地区有 $N$（$2 \le N \le 10^5$）个十字路口和 $M$（$1 \le M \le 5 \times 10^5$）条限定通行方向的道路。第 $i$ 条道路连接路口 $A_i$（$1 \le A_i \le N$）和 $B_i$（$1 \le B_i \le N$），两个路口之间可能连接有多条道路。允许双向通⾏的道路是将两条单向通⾏的道路隔开所形成的。

John 的家在路口 $1$ 位置，农场在路口 $N$ 的位置。John 可以沿着⼀系列单向道路从家驾车到农场。所有 GPS 系统的底层地图信息都是⼀样的，区别仅在于对每一条道路的通⾏时间计算不同。对于第 $i$ 条道路第一套 GPS 系统计算通行时间为 $P_i$ 个单位时间，而第二套 GPS 系统则给出 $Q_i$ 个单位时间。（所有道路的通行时间都是范围在 $1$ 到 $10^5$ 之间的整数）John 想要驾车从家到农场。可是，一路上 GPS 系统总是不厌其烦的提醒 John（请从路口 $X$ 开往路口 $Y$），这是由于 John 选取了某套 GPS 系统建议的路径，而另一套 GPS 系统则认为这不是从路口 $X$ 到农场的最短路径。我们称之为 GPS 系统的抱怨。

请你计算一下如果 John 选择合适的路径到达农场能听到的最少 GPS 系统的抱怨数。如果 John 经过某条道路两套 GPS 系统都发出抱怨，则抱怨总数加 $2$。

输入格式

第一行，两个整数 $N$ 和 $M$。

接下来 $M$ 行，其中第 $i$ 行描述了道路 $i$ 的信息：$A_i,B_i,P_i,Q_i$。

输出格式

一个整数，表示 John 一路上能听到的最小抱怨数。

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