Задача №1868. Самолёт
В городе Энске идёт мокрый снег. Несмотря на это, самолёту необходимо отправиться по расписанию. Причина волнения экипажа в том, что снег налипает на крылья, меняя балансировку самолёта, поэтому необходимо что-то предпринять для подготовки самолёта к подъёму в воздух.
В аэропорту Энска довольно запутанная система взлётно-посадочных полос. Пока самолёт проходит те или иные из них, снег может налипнуть на одно из крыльев.
Задача экипажа сейчас состоит в том, чтобы выбрать путь для разгона, минимизирующий разность количеств снега, налипшего на крылья. Напишите программу, вычисляющую наилучший результат, которого возможно достичь.
Входной файл содержит не более 10 тестов. Каждый тест начинается строкой, содержащей два целых числа \(n\) и \(k\) — количество пересечений полос и самих отрезков взлётно-посадочных полос, соответственно (\(2 \le n \le 10\,000\), \(1 \le k \le 10\,000\)). Далее следуют \(k\) строк, каждая из которых описывает часть взлётно-посадочной полосы. Описание состоит из трёх целых чисел \(a\), \(b\) и \(w\) (\(1 \le a \ne b \le n\), \(-1 \le w \le 1\)). Такое описание соответствует части полосы, соединяющей пересечения \(a\) и \(b\), на которой снег липнет к левому крылу (\(w = -1\)), к правому крылу (\(w = 1\)), или где снег не налипает на крылья (\(w = 0\)).
Заметьте, что из-за экологических проблем снег имеет довольно сложную структуру (более того, учёные полагают, что он обладает мыслительными способностями...) Именно поэтому крыло, к которому липнет снег, не зависит от направления движения по полосе.
Самолёт начинает движение на пересечении номер \(1\) и должен взлететь в пересечении номер \(n\). Путь самолёта должен проходить по полосам, переход с одной полосы на другую (возможно, ту же самую) осуществляется на пересечении, которым они обе соединяются с какими-то ещё.
Других ограничений на перемещение самолёта нет, способ взлететь существует во всех тестах.
Для каждого теста выведите минимальную возможную разность. Следуйте формату, приведённому в примере, как можно точнее.
2 1 2 1 -1 5 5 1 2 1 2 3 0 2 4 0 5 3 -1 5 3 1
Case #1: The plane needs to bear the difference of 1. Case #2: The plane needs to bear the difference of 0.