시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 512 MB 193 75 (39%) 61
문제
삼성고등학교의 기숙사는 N개의 방으로 이루어져 있고, 각 기숙사 방에는 한 명의 학생이 살고 있다. 편의상 각 학생에 1번부터 N번까지 번호를 붙이도록 하자. 하루는 X번 학생의 기숙사 방에서 파티를 열기로 하였다. 각 학생들은 각자의 기숙사 방에서 X번 학생의 기숙사 방까지 갔다가 파티를 마치고 돌아오려 한다. 이 때, 이동하는 경로는 최단 경로로 이동한다. 다만 문제는 각 기숙사를 잇고 있는 M개의 길이 일방통행이라는 점이다. 결국, 그 기숙사 방까지 가는 경로와 그 기숙사 방에서 돌아오는 경로가 다를 수 밖에 없다. 각 길의 정보가 주어졌을 때, 파티에 참석했다가 돌아오는데 소요되는 시간이 가장 긴 학생의 소요 시간을 알아내자.
입력
첫 번째 줄에 학생의 수 N, 길의 수 M, 파티를 여는 기숙사 방에 있는 학생의 번호 X가 주어진다. (1 ≤ N ≤ 50,000, 1 ≤ M ≤ 500,000) 두 번째 줄부터 M개의 줄에 걸쳐 각 길의 정보 s, e, t가 주어진다. s는 일방통행 길이 시작되는 기숙사 방의 번호이고, e는 길이 끝나는 기숙사 방의 번호이다. t는 그 길을 지나가는데 걸리는 소요 시간이다. 소요 시간은 1 이상 100 이하이다.
출력
첫 번째 줄에 파티에 참석했다가 돌아오는데 소요되는 시간이 가장 긴 학생의 소요 시간을 출력한다.
힌트
#### 예제 입력 ``` 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 ``` #### 예제 출력 ``` 10 ```