Как создать хорошую игру
Компания по разработке видеоигр 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. Также можно предположить, что никакие два пути не соединяют одну и ту же пару контрольных точек.
Выходные данные
Выведите строку, содержащую максимальное количество новых этапов, которые можно добавить в игру при следующих ограничениях:
Вы не можете увеличивать максимальное возможное количество этапов в одной игре (т.е. длину самого длинного маршрута до конца).
Вы не можете изменять структуру путей (т.е. как контрольные точки соединяются друг с другом).
Вы не можете удалять ни один этап, который уже существует в бета-версии.