Миньоны развлекаются

Грю ушел в магазин, и теперь миньонам очень скучно и нечего делать. Они решили занять себя и придумали соревнование, участвовать в котором согласились абсолютно все.

Суть соревнования заключается в следующем. На карте лаборатории Грю отмечено n контрольных точек. Между ними проведено m двусторонних дорожек, на каждой из которых лежит несколько бананов. Миньонам предлагается начать свой путь в любой контрольной точке, побегать по дорожкам, а потом вернуться в исходную точку. При этом миньон никогда не пробегает по одной дорожке более одного раза.

Пусть миньон пробежал какой-то такой циклический путь и прошел по дорожкам, на которых лежало c1, c2, ..., ck бананов соответственно. Тогда он получит за этот путь количество очков, равное min(c1, c2, ..., ck) + max(c1, c2, ..., ck).

Дэйв — один из участников этого соревнования, и он очень хочет победить. Поэтому он обратился к вам за помощью, чтобы вы помогли ему найти оптимальный циклический путь, то есть путь, за который он получит максимальное количество очков. Не отказывайте этому милому созданию, помогите ему!

В первой строке находятся два целых числа n и m (1 ≤ n, m ≤ 105) — количество контрольных точек и количество дорожек между ними.

В следующих m строках дано описание дорожек между контрольными точками — в i-й из них написано три числа v, u, w (1 ≤ v, u ≤ n; v ≠ u; 0 ≤ w ≤ 109) — номера контрольных точек, между которыми проходит i-я дорожка, и количество бананов на ней.

Выведите ответ на задачу — максимальное значение суммы минимального и максимального количества бананов среди всех циклических путей. Если на карте нет ни одного циклического пути, выведите 0.