Problem
엔은 버섯을 모으기 위해 버섯 숲으로 갑니다.
버섯 숲에는 n개의 나무를 연결하는 m 방향의 길이 있습니다. 버섯은 모든 길에서 자랍니다. En은 길을 따라 걸을 때 그 길에 있는 모든 버섯을 줍습니다. 하지만 버섯 숲은 비옥한 토양을 가지고 있어 버섯이 환상적인 속도로 자랍니다. En이 길에서 버섯 따기를 마치자마자 새로운 버섯이 자랍니다. 즉, En은 i번째 경로를 따라 통과한 후 이 경로를 통과하기 전보다 버섯이 더 적게 자랍니다. 따라서 경로에 처음에 x개의 버섯이 있는 경우 En은 첫 번째 패스에서 x개의 버섯을 수집하고 두 번째 패스에서 x - 1개의 버섯을 수집하고 세 번째 패스에서 x - 1 - 2개의 버섯을 수집합니다. 에. 단, 버섯의 개수는 0개 미만이 될 수 없습니다.
예를 들어 처음에는 경로에서 9개의 버섯이 자라게 합니다. 그런 다음 En이 수집할 버섯의 수는 1에서 4까지의 패스에 대해 9, 8, 6, 3입니다. 다섯 번째 패스부터 En은 이 경로에서 아무것도 수집할 수 없습니다(하지만 여전히 걸을 수 있음).
엔은 나무부터 시작하기로 했다. 설명된 경로를 따라서만 이동하여 수집할 수 있는 버섯의 최대 개수는 얼마입니까?
입력:
첫 번째 줄은 두 개의 정수 n과 m을 포함합니다(1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — 버섯 숲의 나무 수와 방향성 경로의 수.
다음 m행 각각은 세 개의 정수 x, y 및 w(1 ≤ x, y ≤ n, 0 ≤ w ≤ 10
8)를 포함합니다. ) 초기에 w 버섯이 있는 나무 x에서 나무 y로 이어지는 경로를 설명합니다. 한 나무에서 같은 나무로 이어지는 경로와 같은 나무 쌍을 연결하는 여러 경로가 있습니다.
마지막 줄에는 단일 정수 s (1 ≤ s ≤ n) — 엔의 시작 위치.
출력:
단일 정수 인쇄 — En이 이동 중에 수집할 수 있는 최대 버섯 수입니다.
예:
<몸>
| 입력 |
출력 |
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개의 버섯을 모을 수 있습니다. 그 이후에는 En이 수집할 버섯이 없습니다.
두 번째 예에서 En은 나무 3으로 이동하여 나무 1에서 나무 3으로 가는 경로에서 8개의 버섯을 선택할 수 있습니다.