题目描述

农民约翰最近在网上买了一辆新车，但在匆忙中，他在为汽车选择额外功能时意外地点击了"提交"按钮两次，结果汽车最终配备了两个${GPS}$导航系统！

更糟糕的是，这两个系统经常在${FJ}$应该采取的路线上做出相互冲突的决定。

${FJ}$所在地区的地图由${N}$个十字路口${（2<=N<=10000）}$和${M}$条定向道路${（1<=M<=50000）}$组成。道路${i}$连接交叉口${A_i（}$${1<=A_i<=N）}$和${B_i（}$${1<=B_i<=N）}$。

多条道路可以连接同一对十字路口，双向道路（一条允 许双向行驶）由两条方向相反的独立定向道路表示。${FJ}$的房子位于十字路口${1，}$他的农场位于十字路口${N}$。沿着一系列有方向的道路可以从他的房子到达 农场。

两个${GPS}$装置使用上述相同的基础地图；然而，他们对每条道路的行驶时间有不同的概念。

道路${i}$根据第一个${GPS}$单位采用${P_i}$时间单位进 行穿越，根据第二个单位采用${Q_i}$时间单位进行穿越（每个行程时间是${1}$到${100000}$范围内的整数）。

${FJ}$想从家里去农场。

然而，每当${FJ}$ 沿着一条${GPS}$单元认为不是从${X}$到农场的最短路线的一部分的道路（例如，从${X}$交叉口到${Y}$交叉口）行驶时，每个${GPS}$单元都会大声抱怨（如果${FJ}$走的是两个单元都不喜欢的道路，则两个${GPS}$单元甚至可能都会抱怨）。

如果${FJ}$选择了合适的路线，请帮助他确定可能收到的投诉总数。如果当${FJ}$沿着道路行驶时，两个${GPS}$装置都发出投诉，则这将计入总数的${+2}$。

输入格式

第${1}$行：整数${N}$和${M}$。

第一行用四个整数描述道路一：${A_i B_i P_i Q_i}$。

输出格式

第${1}$行：如果${FJ}$从家到农场的路线最佳。

样例

输入样例

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

提示

输入详细信息： 有${5}$个十字路口和${7}$条定向道路。第一条路连接从十字路口${3}$到十字路口${4}$；第一个${GPS}$认为这条路需要${7}$个穿越 时间单位，第二个${GPS}$认为需要${1}$个穿越时间单位时间等。

输出详细信息： 如果${FJ}$遵循路径${1->2->4->5，}$则第一个${GPS}$报修${on1->2}$路（它更喜欢${1->3}$路）。

然而，对于路线${2->4->5}$的其 余部分，两个${GPS}$都很高兴，因为这是一个根据每个${GPS}$从${2}$到${5}$的最短路线。