시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 13 | 2 | 1 | 8.333% |
Грю ушел в магазин, и теперь миньонам очень скучно и нечего делать. Они решили занять себя и придумали соревнование, участвовать в котором согласились абсолютно все.
Суть соревнования заключается в следующем. На карте лаборатории Грю отмечено 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.
3 3 1 2 1 2 3 1 3 1 1
2
4 4 1 2 1 2 3 2 3 1 1 1 4 100
3
4 5 1 2 2 2 3 1 3 1 1 1 4 2 4 2 2
4
2 1 1 2 1
0
Contest > Russian Code Cup > 2015 > RCC 2015 Warm-up D번