집결지 왕복

N개의 도시와 M개의 단방향 도로가 있다. 각 도로는 이동 시간이 정해져 있다. 재난 대피 훈련을 위해 모든 도시의 주민이 지정된 집결지 X로 이동했다가 자신의 도시로 돌아와야 한다.

각 도시에서 집결지 X까지 갔다가 돌아오는 왕복 시간 중 가장 오래 걸리는 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, X가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 둘째 줄부터 M개의 줄에 출발 도시, 도착 도시, 이동 시간이 공백으로 구분되어 주어진다. (1 ≤ 이동 시간 ≤ 100)

출력

가장 오래 걸리는 왕복 시간을 출력한다.

제한

• 모든 도시에서 집결지로의 경로, 집결지에서 모든 도시로의 경로가 반드시 존재한다.

입출력 예시

입력 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

출력 1

10