부서진 문의 복수

JAG 왕국에는 $N$개의 도시와 $M$개의 양방향 도로가 있다. $i$번째 도로 $(u_i, v_i, c_i)$는 도시 $u_i$와 도시 $v_i$를 잇고 길이는 $c_i$이다. JAG 왕국의 시민인 당신은 어느 날 도시 $S$에서 출발해 도시 $T$로 가기로 했다. 그런데 왕국의 도로 가운데 하나가 지금 공사 중이라 지나갈 수 없다는 사실을 알고 있다. 어느 도로인지는 모른다. 어떤 도로가 공사 중인지는 그 도로가 잇는 두 도시 중 한 곳에 있을 때에만 알 수 있다.

최악의 경우에 이동하는 경로의 총 길이가 최소가 되도록 하라. 출발하기 전에 경로를 정해 둘 필요는 없고, 다음에 갈 곳은 언제든지 그때그때 정할 수 있다. 최악의 경우에 도시 $T$에 도착할 수 없으면 -1을 출력한다.

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

N M S T
u1 v1 c1
.
.
.
uM vM cM

첫째 줄에 네 정수 $N$, $M$, $S$, $T$가 주어진다. $N$은 도시의 수 ($2 \le N \le 100{,}000$), $M$은 양방향 도로의 수 ($1 \le M \le 200{,}000$), $S$는 출발 도시 ($1 \le S \le N$), $T$는 도착 도시 ($1 \le T \le N$, $S \ne T$)이다. 이어지는 $M$개 줄은 도로 정보이다. 그중 $i$번째 줄에는 세 정수 $u_i$, $v_i$, $c_i$가 주어지며, $i$번째 도로가 도시 $u_i$와 도시 $v_i$를 ($1 \le u_i, v_i \le N$, $u_i \ne v_i$) 길이 $c_i$ ($1 \le c_i \le 10^9$)로 잇는다는 뜻이다. 공사 중인 도로가 없다면 모든 도시 쌍은 서로 연결되어 있다고 가정해도 된다. 즉, 모든 도시 $x$와 $y$에 대해 주어진 도로만으로 $x$에서 $y$로 가는 경로가 적어도 하나 있다. 같은 두 도시를 잇는 도로가 두 개 이상 주어지지는 않는다. 즉, $1 \le i < j \le M$인 모든 $i$, $j$에 대해 $\{u_i, v_i\} \ne \{u_j, v_j\}$이다.

최악의 경우에 이동하는 경로의 총 길이의 최솟값을 출력한다. 최악의 경우에 도시 $T$에 도착할 수 없으면 -1을 출력한다.