눈이 많이 내린 어느 날, 드론 배송 회사는 도시의 창고 \(s\) 에서 출발하여 고객 집 \(e\) 로 물건을 배송하려고 한다. 그런데 이번 배송에는 반드시 거쳐야 하는 중간 충전소 \(w\) 가 있다. 드론은 충전소 \(w\) 를 한 번 이상 방문한 뒤 목적지 \(e\) 에 도착해야 한다.

도시에는 \(n\) 개의 교차점과 \(m\) 개의 양방향 도로가 있으며, 각 도로를 지나는 데 드는 에너지가 주어진다. 창고 \(s\) 에서 출발하여 충전소 \(w\) 를 반드시 거쳐 목적지 \(e\) 까지 도달하는 데 필요한 최소 에너지를 구하여라.

같은 교차점이나 도로를 여러 번 지나도 상관없다. 도달이 불가능하면 \(-1\) 을 출력한다.

\(2 \le n \le 60{,}000\), \(1 \le m \le 180{,}000\), \(1 \le w \le 1{,}000\)

첫째 줄에 교차점의 수 \(n\) 과 도로의 수 \(m\) 이 주어진다. (\(2 \le n \le 60{,}000\), \(1 \le m \le 180{,}000\))

다음 \(m\) 개의 줄에 각각 세 정수 \(u\ v\ w\) 가 주어지며, 교차점 \(u\) 와 \(v\) 를 잇는 에너지 \(w\) 의 양방향 도로를 의미한다. (\(1 \le u, v \le n\), \(u \ne v\), \(1 \le w \le 1{,}000\))

마지막 줄에 출발점 \(s\), 충전소 \(w\), 목적지 \(e\) 가 주어진다.

최소 에너지를 한 줄에 출력한다. 도달이 불가능하면 \(-1\) 을 출력한다.

riseoj 작성

출처 Original