무료 항공권 한 장

피터는 ICPC 월드 파이널에 다녀왔다. 돌아오는 비행기가 초과 예약되는 바람에 피터는 자리를 잃었고, 항공사는 보상으로 원하는 두 도시를 잇는 무료 항공권 한 장을 주었다.

피터는 벌써 내년 여행을 계획하고 있다. 이동은 자동차로 하지만, 주어진 항공편 가운데 하나를 골라 여정의 한 구간에 무료 항공권을 쓸 수 있다. 항공권을 쓴 구간은 비용이 들지 않는다.

도시를 잇는 도로망과 각 도로의 기름값, 그리고 이용할 수 있는 항공편 목록이 주어진다. 피터가 출발 도시에서 내년 목적지까지 가는 데 드는 최소 비용을 구하여라.

입력은 테스트 케이스 하나로 이루어진다. 첫째 줄에 다섯 정수 $n$, $m$, $f$, $s$, $t$가 공백으로 구분되어 주어진다. $n$은 도시의 수 ($0 < n \le 50\,000$), $m$은 도로의 수 ($0 \le m \le 150\,000$), $f$는 항공편의 수 ($0 \le f \le 1\,000$), $s$는 피터가 출발하는 도시의 번호 ($0 \le s < n$), $t$는 피터가 도착하려는 도시의 번호 ($0 \le t < n$)이다. 도시 번호는 $0$부터 $n - 1$까지이다.

다음 $m$개 줄에는 도로 하나의 정보가 세 정수 $i$, $j$, $c$ ($0 \le i, j < n$, $i \ne j$, $0 < c \le 50\,000$)로 주어진다. 도시 $i$와 도시 $j$를 잇는 도로가 있고 이 도로를 지나는 데 $c$센트가 든다는 뜻이다. 도로는 양방향 모두 같은 비용으로 이용한다. 도로 정보는 모두 서로 다르다.

이어지는 $f$개 줄에는 항공편 하나의 정보가 두 정수 $u$, $v$ ($0 \le u, v < n$, $u \ne v$)로 주어진다. 도시 $u$에서 도시 $v$로 가는 항공편이 있다는 뜻이다. $v$에서 $u$로 가는 항공편은 따로 한 줄로 주어지지 않는 한 없다. 항공편 정보는 모두 서로 다르다.

피터가 항공편을 많아야 한 번 이용해서 출발 도시에서 목적지까지 가는 데 드는 최소 비용을 센트 단위로 출력한다. 목적지까지 가는 경로는 항상 존재한다.