The Hungary Games

헝가리 게임에 오신 것을 환영합니다! 부다페스트의 거리는 복잡하게 얽힌 일방통행 도로망을 이룹니다. 당신은 리얼리티 TV 쇼의 일부로 이 거리를 질주하는 경주에 강제로 참가하게 되었습니다. 출발점은 세체니 온천(줄여서 $s$), 도착점은 귈 바바의 무덤(줄여서 $t$)입니다.

당연히 당신은 최대한 빨리 완주하고 싶습니다. 기록이 좋을수록 더 많은 광고 계약을 따낼 수 있기 때문입니다. 하지만 함정이 있습니다. $s$에서 $t$까지 최단 경로를 택할 만큼 영리한 사람은 팔뵐지 동굴계에 던져져 국보로 보관됩니다. 당신은 이 운명을 피하면서도 가능한 한 빠르고자 하므로, 엄밀하게 두 번째로 짧은 $s$-$t$ 경로를 택해야 합니다.

$s$에서 $t$까지 엄밀하게 두 번째로 짧은 경로의 길이를 계산하는 프로그램을 작성하세요. 이런 경로는 때때로 같은 노드를 두 번 이상 방문하기도 합니다. 가령 같은 간선을 왕복하는 경우가 그렇습니다.

첫째 줄에 두 정수 $N$과 $M$이 주어집니다. $N$은 부다페스트의 노드 수, $M$은 간선 수입니다. 노드는 $1, 2, \ldots, N$으로 번호가 매겨지며, 노드 $1$이 $s$, 노드 $N$이 $t$입니다.

이어지는 $M$개의 줄에는 각각 세 정수 $A\ B\ L$이 주어지며, 이는 $A$에서 $B$로 향하는 길이 $L$의 일방통행 도로를 나타냅니다. 모든 줄에서 $A \ne B$이고, 순서쌍 $(A, B)$는 서로 다릅니다.

$s$에서 $t$까지 엄밀하게 두 번째로 짧은 경로의 길이, 즉 $s$에서 $t$까지 모든 경로의 총길이 중 서로 다른 값들 가운데 두 번째로 작은 값을 출력합니다. $s$에서 $t$까지 서로 다른 경로 길이가 두 가지 미만이면 $-1$을 출력합니다.

모든 길이 $L$은 $1 \le L \le 10000$인 양의 정수입니다. 전체 테스트 케이스의 50%에서는 $2 \le N \le 40$, $0 \le M \le 1000$입니다. 모든 테스트 케이스에서 $2 \le N \le 20000$, $0 \le M \le 100000$입니다.