Як створити хорошу гру
Компанія з розробки відеоігор під назвою ICPC (International Company for Playing and Competing) працює над новою аркадною грою. Ця гра має безліч відгалужень, що робить її цікавою для всіх гравців, оскільки вони можуть обирати маршрути відповідно до своїх навичок. Новачки можуть обрати легший шлях, щоб насолодитися грою, а досвідчені гравці можуть вибрати складніші маршрути для досягнення високих результатів.
У грі є багато контрольних точок, з'єднаних шляхами. Кожен шлях складається з кількох етапів, і проходження цих етапів веде гравців до наступної контрольної точки. Гра завершується, коли гравці досягають певної контрольної точки. На деяких контрольних точках гравці можуть обирати напрямок, тому маршрути розходяться. Іноді різні маршрути з'єднуються в одній контрольній точці. Шляхи між контрольними точками є спрямованими, і немає циклів (щоб уникнути нескінченної гри). Іншими словами, структура гри може бути представлена як DAG (орієнтований ациклічний граф), якщо розглядати шляхи між контрольними точками як орієнтовані ребра.
Нещодавно команда розробників завершила бета-версію гри і отримала відгуки від інших команд. Відгуки були загалом позитивними, але містили деякі зауваження. Деякі тестувальники зазначили, що деякі маршрути були занадто короткими в порівнянні з найдовшими. Дійсно, у бета-версії кількість етапів у грі може значно варіюватися залежно від обраного маршруту. Дизайнери гри скаржилися, що багато їхніх ідей не були реалізовані в бета-версії через обмежений час розробки. Вони хотіли б додати більше етапів у фінальну версію.
Однак, додавання нових етапів не є простим завданням. Це аркадна гра — якщо час гри буде занадто довгим, це може знизити прибуток, і власники аркад можуть бути незадоволені. Тому найдовший маршрут у фінальній версії не може бути довшим, ніж у бета-версії. Крім того, продюсер гри не хоче змінювати структуру шляхів (тобто, як контрольні точки з'єднуються одна з одною), оскільки це вимагало б переписування сценарію, запису голосів, створення нових кат-сцен тощо.
З огляду на це, продюсер вирішив додати якомога більше нових етапів, зберігаючи максимальну можливу кількість етапів в одній грі та незмінну структуру шляхів. Скільки нових етапів можна додати до гри?
Вхідні дані
N M x_1 y_1 s_1 ... x_M y_M s_M
Перший рядок вхідних даних містить два додатні цілі числа N та M (2 ≤ N ≤ 100, 1 ≤ M ≤ 1000). N вказує на кількість контрольних точок, включаючи початок і закінчення гри. M вказує на кількість шляхів між контрольними точками.
Наступні M рядків описують структуру шляхів у бета-версії гри. i-й рядок містить три цілі числа x_i, y_i та s_i (0 ≤ x_i < y_i ≤ N-1, 1 ≤ s_i ≤ 1000), які описують, що існує шлях від контрольної точки x_i до y_i, що складається з s_i етапів. Щодо індексів контрольних точок, зауважте, що 0 вказує на початок гри, а N-1 вказує на закінчення гри. Ви можете припустити, що для кожної контрольної точки i існує маршрут від початку до закінчення, який проходить через контрольну точку i. Ви також можете припустити, що жодні два шляхи не з'єднують одну й ту ж пару контрольних точок.
Вихідні дані
Виведіть рядок, що містить максимальну кількість нових етапів, які можна додати до гри за наступних умов:
Ви не можете збільшити максимальну можливу кількість етапів в одній грі (тобто довжину найдовшого маршруту до закінчення).
Ви не можете змінювати структуру шляхів (тобто, як контрольні точки з'єднуються одна з одною).
Ви не можете видаляти жоден етап, який вже існує в бета-версії.