【题目描述】

约翰在他的新车上装了两个导航系统(GPS)，但这两个GPS选择的导航线路常常不同，约翰很是恼火。
约翰所在的小镇地图由N个路口和M条单向道路构成，两个路口间可能有多条道路相连。约翰的家在1号路口，他的农场在N号路口。约翰从家出发，可以经过一系列的道路，最终到达农场。
两个GPS用的都是上述地图，但是，它们计算时间的算法不同。比如，经过第i条道路，1号GPS计算出的时间是P_i分钟,而2号GPS算出的时间是Q_i分钟。
约翰想要驾车从家到农场，但是，如果一个GPS认为约翰当前行走的这条路不在它算出的最短路径中，该GPS就会大声抱怨约翰走错了路。更倒霉的是，有可能两个GPS会同时抱怨约翰当前走的路不是它们推荐的。
请帮助约翰计算，从家到农场过程中，选择怎样的路径才能使得GPS抱怨的次数最少，请算出这个最少的抱怨次数。如果一条路上两个GPS都在抱怨，算两次(+2)抱怨。

【输入格式】

第1行： 两个空格间隔的整数：N、M
接下来M行，每行描述一条道路。
第i行描述第i条道路，由四个空格间隔的整数构成，Ai,Bi,Pi,Qi,分别表示该条道路的起点、终点、1号GPS计算的耗时、2号GPS计算的耗时。

【输出格式】

第 1行： 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 -> 4 -> 5, 1号GPS会在1 -> 2 抱怨 (它会推荐走1 -> 3 这条路). 但是, 剩下的路径2 -> 4 -> 5, 两个 GPS 都不会抱怨, 因为它们算出的从2到5最短路径都是走这条路。

【数据范围】

对于30% 的数据，1<= N <=20 1<= M <=20
对于100%的数据，1<= N <=10000 ,1 <= M <= 50000 ,0<=Pi,Qi<=100000

【限制】

本题时间限制1s，空间限制128MB（128000KB），共10个测试点，每个10分，忽略多余空格和换行。