Description

农民约翰最近网购了一辆汽车，由于他在网购时，不小心选择了汽车的特殊配置，导致这辆车被安装了两个汽车导航系统，更糟糕的是，这两个汽车导航系统在约翰开车途中，经常给出不一样的道路提示。 约翰所居住地区的地图由N个点（顶点的编号1..N)和M条有向边（道路）组成，两点之间可能有多条边。约翰的家在地图1号点位置，他农场的位置在地图N号点位置。他经常从他的家开车到农场。 汽车的两个导航系统都是安装了上面描述的地图，但是两个导航系统在经过同一条道路时提示花费的时间是不一样的。例如经过第i条路时，第一个导航系统提示花费Pi的单位时间，第二个导航系统提示花费Qi的单位时间。 约翰想开车从他家到他的农场。但是，如果他经过的道路X到Y不是X到农场最短路径的边，导航系统都会发出1次大声的警告声，有时候经过的道路（X->Y)都不是两个导航系统从X到农场的最短路的边，就会发出2次警告声。 请帮忙约翰计算从他家开车到农场，这两个导航系统总共最少会发出多少次警告声？

Input Format

第一行两个整数N和M 第二行到M+1行，每行描述每条边的信息Ai到Bi的边，及Pi和Qi。Pi和Qi的范围都是（1..100,000），(1 <= Ai <= N) and (1 <= Bi <= N).

Output Format

从顶点1到N，最少需要受到多少次警告。

Sample

【样例输入】

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到N选择走的路径是1 -> 2 -> 4 -> 5，第一个导航系统在经过边1—>2的时候，会发出警告1次，剩下的路线2 -> 4 -> 5,在两个系统中都是最短路，就不发出警告了。

Hint

对于100%的数据，2 <= N <= 10,000,1 <= M <= 50,000 数据有一定梯度。