Задача
Эн идет в свой Грибной лес собирать грибы.
В Грибном лесу m ориентированных дорожек, соединяющих n деревьев. На каждой дорожке растут грибы. Когда Эн проходит по дорожке, он собирает все грибы на этой дорожке. Однако, в Грибном лесу такая плодородная почва, что грибы растут с фантастической скоростью. Новые грибы вырастают, как только Эн заканчивает собирать грибы на дорожке. А именно, после того, как Эн проходит по дорожке в i-й раз, вырастает на i грибов меньше, чем было до этого прохода. Таким образом, если на дорожке изначально было x грибов, то Эн соберет x грибов в первый проход, x - 1 гриб во второй, x - 1 - 2 гриба в третий и так далее. Однако, количество грибов не может стать меньше 0.
Например, пусть изначально на дорожке росло 9 грибов. Тогда количество грибов, которое соберет Эн, равно 9, 8, 6 и 3 для проходов с первого по четвертый. Начиная с пятого прохода и далее Эн ничего не сможет собрать с этой дорожки (но все еще может по ней ходить).
Эн решил начать от дерева s. Какое максимальное количество грибов он может собрать, передвигаясь только по описанным дорожкам?
Входные данные:
Первая строка содержит два целых числа n и m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — количество деревьев и количество ориентированных дорожек в Грибном лесу, соответственно.
Каждая из следующих m строк содержит три целых числа x, y и w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10
8), описывающих дорожку, которая ведет от дерева x к дереву y с w грибами изначально. Возможны дорожки, которые ведут от дерева к нему же, а также несколько дорожек, соединяющих одну и ту же пару деревьев.
Последняя строка содержит одно целое число s (1 ≤ s ≤ n) — начальную позицию Эна.
Выходные данные:
Выведите одно целое число — максимальное число грибов, которое может собрать Эн на своем пути.
Примеры:
| Входные данные |
Выходные данные |
2 2
1 2 4
2 1 4
1 |
16 |
3 3
1 2 4
2 3 3
1 3 8
1 |
8 |
Пояснения:
В первом примере Эн может три раза пройти по кругу и собрать 4 + 4 + 3 + 3 + 1 + 1 = 16 грибов. После этого не будет грибов, которые Эн может собрать.
Во втором примере Эн может пойти к дереву 3 и собрать 8 грибов на дорожке от дерева 1 до дерева 3.