Найкращий лижний маршрут

Джон обожнює зиму. Щозими він разом із друзями катається на лижах. Для цього вони орендують вертоліт, який доставляє їх на будь-яку гору в Альпах. Звідти вони спускаються мальовничими схилами по незайманому снігу.

Звісно, вони хочуть кататися лише за найкращих умов. Для цього вони використовують комбінований показник умов, щоб оцінити всі доступні схили в будь-який день.

Чи зможеш ти допомогти їм знайти найвражаючий маршрут?

Вхідні дані

У першому рядку записані два цілі числа $n(2\le n\le 1000)$ і $m(1\le m\le 5000)$, де $n$ — кількість ($1$-індексованих) точок з'єднання між схилами, а $m$ — кількість схилів.

Кожен з наступних $m$ рядків містить три цілі числа $s,t,c(1\le s,t\le n,1\le c\le 100)$, що представляють схил від точки $s$ до точки $t$ з мірою умови $c$.

Точки без вхідних схилів — це гірські вершини з красивими пейзажами, точки без вихідних схилів — долини. Вертоліт може приземлитися в будь-якій точці з'єднання, тому друзі можуть почати і закінчити тур у будь-якій точці на свій розсуд. Усі схили йдуть вниз, тому незалежно від того, де вони починаються, вони не можуть знову досягти тієї ж точки після проходження будь-якого з схилів.

Вихідні дані

Виведіть одне число — максимальну суму мір умов на шляху, яку можуть пройти друзі.

Приклади