시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 64 MB 1 1 (100%) 1
문제
헝가리 게임에 오신것을 환영합니다! 부다페스트 거리는 일방향 도로가 트위스트 네트워크 모양을 하고있습니다. 당신은 당신은 "현실적인 TV" 쇼의 일환으로 이 거리를 달리도록 강요받았는데, 스체이 서멀 배스 (줄여서 s)에서 시작해 톰브 오프 길 바바(줄여서 t)로 끝나게 됩니다. 당연히, 당신은 레이스의 완주를 가능한 빨리 빠르게 하고싶고, 왜냐하면 더 많은 판촉 계약을 얻을수 있기 때문입니다. 하지만, 한가지 알아야 할 것이 있습니다: s-t사이를 최단거리로 지날만큼 충분히 똑똑한 사람은 팔블라이 동굴 시스템에 던져져 국보로 보존 될 것입니다. 이 운명을 피하고 싶지만, 여전히 최대한 빠르게 도착하고 싶습니다. s-t사이 경로 중 엄격히 두번째 최단거리인 경로를 계산하는 프로그램을 작성하십시오. 가끔 엄격히 두번째 최단거리 경로가 같은 정점을 여러번 반복할 수도 있습니다; 예제 2번을 확인하세요. 제한 모든 길이 L은 1에서 10000사이의 양의 정수입니다. 50%의 테스트 케이스는 2<=N<=40, 0<=M<=1000을 만족합니다. 모든 테스트 케이스는 2<=N<=20000와 0<=M<=100000를 만족합니다.
입력
첫번째 줄에는 N, M이 주어지는데, N은 부다페스트의 정점 갯수이고 M은 간선갯수입니다. 각 정점은 1, 2, ..., N; 1번 정점은 s; N번 정점은 t입니다. 그 뒤, M개의 줄에 A B L형태가 주어지는데, 이는 A 에서 B로가는 길이 L짜리 단방향 도로가 있다는 뜻입니다. A != B이고 모든 순서있는 쌍 (A,B)는 다르다고 가정해도 좋습니다.
출력
엄격히 두번째 최단거리 루트의 길이를 출력합니다. 만약 s-t사이에 두개 미만의 경로 길이만이 가능하면 -1을 출력합니다.
힌트
입력예제1 ``` 4 6 1 2 5 1 3 5 2 3 1 2 4 5 3 4 5 1 4 13 ``` 출력예제1 ``` 11 ``` 예제설명 길이 10짜리 두개의 최단경로가 존재합니다. (1 -> 2 -> 4, 1 -> 3 -> 4) 그리고 엄격히 두번째 최단경로는 1 -> 2 -> 3 -> 4 이며 길이 11입니다. 입력예제2 ``` 2 2 1 2 1 2 1 1 ``` 출력예제2 ``` 3 ``` 예제설명 최단거리는 1->2로 가는 길이 1짜리 입니다. 그리고 엄격히 두번째 최단거리는 1 -> 2 -> 1 -> 2로 총 길이 3입니다.