Фермер Джон недавно купил новую машину с двумя навигационными
системами GPS. Что ещё хуже, они часто конфликтуют при выборе
Маршрута.
Карта региона, в котором живёт ФД представляет собой N перекрёстков
(2 <= N <= 10,000) и M двунаправленных дорог (1 <= M <= 50,000).
Дорога I соединяет перекрёстки Ai (1 <= Ai <= N) и Bi (1 <= Bi <= N).
Множество дорого может соединять одну и ту же пару перекрёстков.
Двунаправленные дороги представлены двумя раздельными
однонаправленными дорогами в противоположных направлениях.
Дом ФД находится в перекрёстке 1, а его ферма распложена в перекрёстке
N. Существует путь из дома на ферму, по серии однонаправленных дорог.
Обе GPS-системы используют карту описанную выше, однако они дают
различные значения времени проезда по каждой дороге. Дорога I
требует Pi единиц времени по первой GPS-системе и Qi единиц времени
по второй (каждая из величин – целое число в интервале 1..100,000).
ФД хочет проехать от дома до фермы. Однако каждая GPS-система громко
оповещает ФД каждый раз, когда ФД выбирает дорогу (например, от
перекрёстка X до перекрёстка Y) которую GPS не считает частью
кратчайшего пути от X до фермы (возможно даже что предупреждение
выдают обе GPS-системы, если ФД выбирает дорогу, которую каждая из
GPS считает не принадлежащей к кратчайшему маршруту).
Пожалуйста, помогите ФД определить минимальное количество предупреждений,
которое он может получить соответствующим выбором маршрута.
Если две SPS-системы предупреждают одновременно, к ответу в этом случае
нужно прибавлять число 2.
PROBLEM NAME: gpsduel
Формат ввода:
* Строка 1: целые числа N и M.
* Строка 2-N+1: Строка i описывает дорогу i четырьмя
целыми числами: Ai Bi Pi Qi.
Примечание
Всего имеется 5 перекрёстков и 7 однонаправленных дорог. Первая
дорога идёт от перекрёстка 3 к перекрёстку 4, первая GPS считает,
что нужно 7 единиц времени для проезда по этой дороге, а вторая GPS
- полагает, что требуется одна единица времени.
Формат вывода:
* Строка 1: Минимальное количество предупреждений, которое
может получить ФД при оптимальном проезде от дома до фермы.
Примечание
Если ФД выберет путь 1 -> 2 -> 4 -> 5, тогда первая GPS пожалуется на
дороге 1->2 (она предпочитает путь 1>3). Однако в остальной части маршрута
2 -> 4 -> 5, обе GPS промолчат, поскольку обе считают такой маршрут
кратчайшим от 2 до 5.