Bumped!

Peter is back from the ICPC World Finals. His return flight was overbooked, he lost his seat, and the airline gave him a voucher good for one free flight between two cities of his choosing.

He is already planning next year's trip. He travels by car, but he may pick one of the listed flights and spend the voucher on that leg of the trip. A leg flown on the voucher costs nothing.

You are given the network of cities and roads, the cost of the gas for each road, and the list of flights that are available. Find the smallest amount of money Peter needs to get from his home town to next year's destination.

The input consists of a single test case. The first line contains five space separated integers $n$, $m$, $f$, $s$, and $t$: the number of cities $n$ ($0 < n \le 50\,000$), the number of roads $m$ ($0 \le m \le 150\,000$), the number of flights $f$ ($0 \le f \le 1\,000$), the number $s$ ($0 \le s < n$) of the city where Peter's trip starts, and the number $t$ ($0 \le t < n$) of the city Peter is traveling to. Cities are numbered from $0$ to $n - 1$.

Each of the next $m$ lines describes one road with three space separated integers $i$, $j$, and $c$ ($0 \le i, j < n$, $i \ne j$, $0 < c \le 50\,000$), meaning that a road connects city $i$ and city $j$ and costs $c$ cents to travel. A road can be used in either direction for the same cost. All road descriptions are distinct.

Each of the next $f$ lines describes one available flight with two space separated integers $u$ and $v$ ($0 \le u, v < n$, $u \ne v$), meaning that a flight from city $u$ to city $v$ is available. That flight does not run from $v$ to $u$ unless a separate line lists it. All flight descriptions are distinct.

Print the minimum number of cents Peter needs to spend to get from his home town to the destination, using at most one flight. A route to the destination always exists.