题目描述

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

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

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

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

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

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

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

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

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

输入格式

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

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

输出格式

第$\red{1}$行：如果$\red{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

提示

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

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

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