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