E. Ральф и грибы
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ральф идет в Грибной лес собирать грибы.

В Грибном лесу m ориентированных дорожек, соединяющих n деревьев. На каждой дорожке растут грибы. Когда Ральф проходит по дорожке, он собирает все грибы на этой дорожке. Однако, в Грибном лесу такая плодородная почва, что грибы растут с фантастической скоростью. Новые грибы вырастают, как только Ральф заканчивает собирать грибы на дорожке. А именно, после того, как Ральф проходит по дорожке в i-й раз, вырастает на i грибов меньше, чем было до этого прохода. Таким образом, если на дорожке изначально было x грибов, то Ральф соберет x грибов в первый проход, x - 1 гриб во второй, x - 1 - 2 гриба в третий и так далее. Однако, количество грибов не может стать меньше 0.

Например, пусть изначально на дорожке росло 9 грибов. Тогда количество грибов, которое соберет Ральф, равно 9, 8, 6 и 3 для проходов с первого по четвертый. Начиная с пятого прохода и далее Ральф ничего не сможет собрать с этой дорожки (но все еще может по ней ходить).

Ральф решил начать от дерева s. Какое максимальное количество грибов он может собрать, передвигаясь только по описанным дорожкам?

Входные данные

Первая строка содержит два целых числа n и m (1 ≤ n ≤ 106, 0 ≤ m ≤ 106) — количество деревьев и количество ориентированных дорожек в Грибном лесу, соответственно.

Каждая из следующих m строк содержит три целых числа x, y и w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 108), описывающих дорожку, которая ведет от дерева 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.