题目描述

小泽准备从路口 $1$ 驾车前往路口 $N$。道路网络共有 $N$ 个路口和 $M$ 条单向道路，第 $i$ 条道路从路口 $A_i$ 通往路口 $B_i$。

车上安装了两套导航系统。对于同一条道路，第一套导航认为行驶时间是 $P_i$，第二套导航认为行驶时间是 $Q_i$。因此，两套导航各自计算出的最短路线可能不同。

当小泽在某个路口选择一条道路时，如果这条道路不属于第一套导航认可的、从当前路口到终点的一条最短路线，第一套导航就会发出一次警告；第二套导航也按照自己的行驶时间独立判断。如果一条道路同时不被两套导航认可，就会收到两次警告。

小泽只关心警告次数，不要求实际行驶时间最短。请计算他从路口 $1$ 到达路口 $N$ 的过程中，最少会收到多少次警告。

输入格式

第一行输入两个整数 $N,M$。

接下来 $M$ 行，第 $i$ 行输入四个整数 $A_i,B_i,P_i,Q_i$，描述一条单向道路及两套导航给出的行驶时间。

输出格式

输出一个整数，表示从路口 $1$ 到路口 $N$ 最少收到的警告次数。

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

2 1
1 2 5 7

0

样例说明 #2

只有一条道路可走，而且它同时是两套导航的最短路线，所以不会收到警告。

3 3
1 2 1 10
2 3 1 10
1 3 5 1

1

数据范围与约定

$2\le N\le10^4$，$1\le M\le5\times10^4$，$1\le A_i,B_i\le N$，$1\le P_i,Q_i\le10^5$。保证从路口 $1$ 可以到达路口 $N$，输入中的所有数均为整数。