时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H所在的城市中有 \(n\) 个路口，编号为 \(1..n\)，同时有 \(m\) 条单向道路连接这些路口，第 \(i\) 条单向道路从路口 \(u_i\) 到路口 \(v_i\)。两个路口之间可能连接有多条道路。小H的家在路口 1，他的公司位于路口 \(n\)。每天他都会驾驶着自己的新车从家到公司上班。

　　小H的新车上装了两套导航系统：B系统和G系统。对于一条从 \(u_i\) 到 \(v_i\) 的道路，B系统估算的通行时间为 \(t_i\)，而G系统估算的通行时间则是 \(w_i\)。当车走到任意一个路口时，两个系统都会建议他接下来继续开往哪个路口。具体来说就是，如果小H的车行驶到路口 \(X\)，B系统会建议他继续开往 \(Y\) 路口，因为它认为 \(X\) 到 \(Y\) 的这条路是 \(X\) 到 \(n\) 的最短路径上的一条道路；而G系统则不认为这样走是从路口 \(X\) 到公司的最短路径上的道路，反而会建议开往 \(Z\)路口会更好！

　　在每个路口，若小H没有听从某个导航系统的建议，该系统会警告小H一次，当然，两个系统的建议都不听从，它们各自都会警告小H一次，即小H会收到两次警告，这让小H烦不胜烦。那么你能不能帮助小H 计算一下，小H选择怎样的上班路线才使得警告次数达到最少，输出这个最少警告次数。

【输入格式】

　　第一行，包含两个整数 \(n\) 和 \(m\)，分别表示路口的数目和道路数量。
　　接下来 \(m\) 行，其中第 \(i+1\) 行描述了道路i的信息，\(u_i ,v_i, t_i, w_i\)，表示第 \(i\) 条单向道路从路口 \(u_i\) 到路口 \(v_i\)，B系统估算的通行时间为 \(t_i\)，G系统估算的则是 \(w_i\)。

【输出格式】

　　一个整数，表示最少的警告次数。

【输入输出样例】

　Input

5 7
1 3 2 20
1 4 17 18
1 2 10 1
2 4 6 5
3 5 4 14
3 4 7 1
4 5 25 3

　Output

1

【样例解释】

　　样例给出的城市交通如如下图，每条道路上的红色数字表示B系统的估算的通行时间，黑色数字表示G系统的估算的通行时间：

　　小H驾车沿着1->2->4->5 的路线行驶，会收到B系统在1->2的道路上的1次警告，因为B系统在1号路口会建议走1->3这条路。而剩下的2->4->5都是满足两套系统推荐的行驶道路。

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤10000\)，\(1≤M≤50000\)，\(1≤t_i,w_i≤100000\)，。

【来源】

　　Mr.he