\(N\)개의 마을에 학생이 한 명씩 살고 있다. 어느 날 모든 학생이 마을 \(X\)에 모여 파티를 열기로 했다.

마을 사이에는 \(M\)개의 단방향 도로가 있다. 학생들은 자신의 마을에서 마을 \(X\)까지 갔다가 다시 자신의 마을로 돌아와야 하며, 갈 때와 돌아올 때 모두 가장 짧은 시간이 걸리는 경로를 이용한다.

파티에 갔다가 돌아오는 데 가장 많은 시간을 사용하는 학생의 왕복 시간을 구하시오.

입력

첫째 줄에 마을의 수 \(N\), 단방향 도로의 수 \(M\), 파티가 열리는 마을의 번호 \(X\)가 공백으로 구분되어 주어진다.

다음 \(M\)개의 줄에 세 정수 \(u\), \(v\), \(t\)가 공백으로 구분되어 주어진다. 이는 마을 \(u\)에서 마을 \(v\)로 이동하는 데 \(t\)의 시간이 걸리는 단방향 도로를 의미한다.

출력

파티에 갔다가 자신의 마을로 돌아오는 데 걸리는 최단 왕복 시간 중 가장 큰 값을 출력한다.

제한 사항

• \(1 \le N \le 1,000\)
• \(1 \le M \le 10,000\)
• \(1 \le X \le N\)
• \(1 \le u, v \le N\)
• \(1 \le t \le 100\)
• 같은 출발 마을과 도착 마을을 갖는 도로는 최대 하나만 주어진다.
• 모든 학생은 마을 \(X\)에 갔다가 자신의 마을로 돌아올 수 있다.
• 정답은 \(2,147,483,647\) 이하이다.

예제 입력 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