파티

1번부터 N번까지 번호가 붙은 N개의 마을이 있고, 각 마을에는 학생이 한 명씩 산다.

어느 날 모든 학생이 X번 마을에 모여 파티를 하기로 했다. 마을 사이에는 M개의 단방향 도로가 있으며, 각 도로를 지나는 데 걸리는 시간이 주어진다.

각 학생은 자기 마을에서 X번 마을까지 갔다가, 파티가 끝난 뒤 다시 자기 마을로 돌아와야 한다. 학생들은 각 방향의 이동 시간을 최소로 하려고 한다.

도로가 단방향이므로 파티에 갈 때의 최단 경로와 집으로 돌아올 때의 최단 경로가 서로 다를 수 있다. 모든 학생 중 최단 왕복 시간이 가장 큰 값을 구하라.

첫째 줄에 정수 N, M, X가 공백으로 구분되어 주어진다.

• 1 <= N <= 1,000
• 1 <= M <= 10,000
• 1 <= X <= N

다음 M개의 줄에는 정수 A, B, T가 주어진다. 이는 A번 마을에서 B번 마을로 가는 단방향 도로가 있으며, 이 도로를 지나는 데 T의 시간이 걸린다는 뜻이다.

• 1 <= T <= 100
• 시작 마을과 도착 마을이 같은 도로는 없다.
• 같은 시작 마을과 도착 마을의 순서쌍에 대해 도로는 최대 하나만 존재한다.

입력은 모든 학생이 자기 마을에서 X번 마을로 갈 수 있고, X번 마을에서 자기 마을로 돌아올 수 있는 경우만 주어진다.

각 학생이 자기 마을과 X번 마을 사이를 왕복하는 데 필요한 최단 시간 중 최댓값을 출력한다.