题目描述

农夫约翰最近在网上购买了一辆新车，但由于匆忙，他在选择汽车的额外功能时不小心点击了两次“提交” 按钮，结果车上配备了两个 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$。

输出格式

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

数据范围与约定

请以题目描述与输入格式中给出的约束为准。

可见测试数据

输入数据 1

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

输入数据 2

5 13
1 2 14 15
2 3 20 1
3 4 12 15
4 5 18 18
4 5 29 15
3 4 7 24
3 4 24 29
1 3 17 1
2 5 18 28
1 5 18 4
2 3 1 4
2 5 1 23
4 5 22 7

输出数据 2

1

输入数据 3

6 14
1 2 16 1
2 3 15 18
3 4 10 13
4 5 1 9
5 6 9 6
2 6 30 18
2 4 17 24
2 3 23 27
3 5 9 6
3 6 12 24
3 4 3 23
3 6 23 6
1 6 7 5
4 6 17 20

输出数据 3

0