Ralph and Mushrooms

Ralph는 Mushroom Forest에서 버섯을 모으려고 한다.

Mushroom Forest에는 n그루의 나무를 연결하는 m개의 유향 경로가 있다. 각 경로에는 버섯이 어느 정도 자란다. When Ralph가 경로를 지나가면 그 경로의 모든 버섯을 모은다. The Mushroom Forest에는 버섯이 놀라운 속도로 자라는 마법의 비옥한 땅이 있다. Ralph가 한 경로에서 버섯 채집을 마치자마자 새로운 버섯이 다시 자란다. 더 구체적으로, Ralph가 한 경로를 i-th번째로 지나간 뒤에는 이번에 지나가기 전보다 i개 적은 버섯이 다시 자란다. 즉, 한 경로에 처음에 x개의 버섯이 있다면 Ralph는 첫 번째에 x개의 버섯을, 두 번째에 x - 1개의 버섯을, 세 번째에 x - 1 - 2개의 버섯을 모으며, 이런 식으로 계속된다. 하지만 버섯의 수는 절대로 0보다 작아질 수 없다.

예를 들어, 한 경로에 처음에 9개의 버섯이 있다고 하자. Ralph가 첫 번째부터 네 번째까지 지나갈 때 그 경로에서 모을 수 있는 버섯의 수는 9, 8, 6, 3이다. 다섯 번째부터는 Ralph가 그 경로에서 어떤 버섯도 모을 수 없지만, 여전히 그 경로를 지나갈 수는 있다.

Ralph는 나무 s에서 출발하기로 했다. 설명된 경로만 사용하여 몇 개의 버섯을 모을 수 있는가?

첫 번째 줄에는 각각 Mushroom Forest에 있는 나무의 수와 유향 경로의 수를 나타내는 두 정수 n, m (1 ≤ n ≤ 106, 0 ≤ m ≤ 106)가 주어진다.

이어서 주어지는 m개의 각 줄에는 세 정수 x, y, w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 108)가 주어지며, 이는 나무 x에서 나무 y로 이어지고 처음에 w개의 버섯이 있는 경로를 나타낸다. 한 나무에서 자기 자신으로 이어지는 경로가 있을 수 있으며, 같은 나무 쌍 사이에 여러 경로가 있을 수도 있다.

마지막 줄에는 Ralph의 시작 위치를 나타내는 정수 하나 s (1 ≤ s ≤ n)가 주어진다.

Ralph가 이동하는 동안 모을 수 있는 버섯 수의 최댓값을 나타내는 정수를 출력한다.

첫 번째 예제에서 Ralph는 순환 경로를 세 번 지나가며 4 + 4 + 3 + 3 + 1 + 1 = 16개의 버섯을 모을 수 있다. 그 후에는 Ralph가 모을 버섯이 남아 있지 않는다.

두 번째 예제에서 Ralph는 나무 3으로 가면서 나무 1에서 나무 3으로 이어지는 경로에서 8개의 버섯을 모을 수 있다.