시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB13218.333%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3 3
1 2 1
2 3 1
3 1 1

예제 출력 1

2

예제 입력 2

4 4
1 2 1
2 3 2
3 1 1
1 4 100

예제 출력 2

3

예제 입력 3

4 5
1 2 2
2 3 1
3 1 1
1 4 2
4 2 2

예제 출력 3

4

예제 입력 4

2 1
1 2 1

예제 출력 4

0