Найкращий лижний маршрут#11627
Джон обожнює зиму. Щозими він разом із друзями катається на лижах. Для цього вони орендують вертоліт, який доставляє їх на будь-яку гору в Альпах. Звідти вони спускаються мальовничими схилами по незайманому снігу.
Звісно, вони хочуть кататися лише за найкращих умов. Для цього вони використовують комбінований показник умов, щоб оцінити всі доступні схили в будь-який день.
Чи зможеш ти допомогти їм знайти найвражаючий маршрут?
У першому рядку записані два цілі числа n~(2 \le n \le 1000) і m~(1 \le m \le 5000), де — кількість (-індексованих) точок з'єднання між схилами, а — кількість схилів.
Кожен з наступних рядків містить три цілі числа s, t, c~(1 \le s, t \le n, 1 \le c \le 100), що представляють схил від точки до точки з мірою умови .
Точки без вхідних схилів — це гірські вершини з красивими пейзажами, точки без вихідних схилів — долини. Вертоліт може приземлитися в будь-якій точці з'єднання, тому друзі можуть почати і закінчити тур у будь-якій точці на свій розсуд. Усі схили йдуть вниз, тому незалежно від того, де вони починаються, вони не можуть знову досягти тієї ж точки після проходження будь-якого з схилів.
Виведіть одне число — максимальну суму мір умов на шляху, яку можуть пройти друзі.
Приклад 1
Приклад 2