NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem10--导航 [guide]

10: 导航 [guide]

Time Limit: 1000 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

过去,每当人们驾车来到一个新的地方时,总要看地图来分辨方向。随着时代的发展,当信息时代来临,几乎每一台手机都拥有了定位功能。在这样的背景下,导航 App就应运而生了。我们只需要在 App 中输入我们的目的地,系统就会为我们自动计算出从当前位置到目的地的最佳路线,并通过语音提示来引导驾驶。如果驾驶员不小心开错了道,App 还会及时发现并通告当前已经偏离了规划路线。小可可所在的 W 城共有 N 个路口,M 条单行道连接其中(双行道可看做两条始点、终点互换的单行道)。对于每条单行道,App 会根据其车流量估算出经过它所需要的时间(这意味着双行道两方向的耗时可能不同)。设定好目的地后,每当车辆到一个路口,App 就会计算出从该路口到目的地的所有最短路,如果最终车辆选择了一条不在任意最短路上的出边,驾驶员就会听到一声报错,并在车行驶到下一个路口时重复上述过程。这一天,小可可驾车带着小兰和小红从 1 号路口往 N 号路口。小兰和小红的手机上装着两款不同的导航 App,虽然它们内置的交通地图相同,但对每条单行道的耗时估计却大相径庭。为了整整小可可,他俩都在出发前设定好了各自 App 上的目的地。假如两款 App 对每条道路的估时都是公开的,现在小可可只想知道,自己究竟要怎么开,才能尽量少听到报错声?如果行驶的一条道路不在两款 App 中任何一款的规划上,小可可会在这条路上听到两声报错。

Input

第一行两个整数 N、M,表示路口数和单行道数;接下来 M 行,每行四个整数 u、v、w 1 、w 2 ,表示从 u 到 v 有一条单行道,它在小兰的 App 上的估计代价是 w 1 ,在小红的 App 上的估计代价是 w 2 。

Output

输出一行一个整数,表示小可可整个行程中,最少听到多少声报错。

Sample Input Copy

4 6
1 2 3 10
4 2 2 2
2 3 7 1
3 4 10 5
2 4 9 7
1 3 5 10

Sample Output Copy

1

HINT