Problem: Chariot Race

Want to try solving this problem? You can submit your code online if you log in or register.

Chariot Race

Time Limit: 0.167 second

It's been a slow century up on Olympus, and the gods are bored. No wars to influence, no affairs to meddle in – the humans are actually getting on rather well with each other. So you decide to have a chariot race.

Since you are gods, these are of course no ordinary chariots. You are racing through the heavens from star to star. Your aim is to be the first to reach the Serene Olive Grove of Alpha Centauri, and Hera has promised the winner a bottle of the famous Sweet Nectar of Elysium. For a prize this magnificent, you are determined to come out victorious.

But even for the gods there are rules. You cannot fly directly to Alpha Centauri, since otherwise Zeus (who has the fastest chariot) would be the clear winner. Instead you have each been given a map of the galaxy telling you which stars you are allowed to fly between.

To add further excitement to the race, some stars are joined by wormholes. Travelling through a wormhole actually takes you back in time. Hera has given Zeus strict instructions not to use the wormholes (being the leader of the gods he must be a good sport), but the rest of you are allowed to use the wormholes as often as you like.

Assume that the race starts at time 0. If you enter a wormhole at time t minutes, then you come out the other end of the wormhole at time t/2 minutes. Since the gods have not yet invented fractions, if t is an odd number then you must round down. For example, if you enter a wormhole at time 10 minutes then you exit at time 5, and if you enter a wormhole at time 15 minutes then you exit at time 7.

Your task is to plot a course through the heavens that allows you to arrive at the Serene Olive Grove of Alpha Centauri at the earliest time possible. Note that you are allowed to pass through Alpha Centauri more than once, e.g., you are allowed to pass through Alpha Centauri at a later time, travel through one or more wormholes and then return at an earlier time to win the race.

Input

Your program should read directly from standard input. The first line of input will contain a single integer N representing the number of stars (1 <= N <= 100). These stars will be numbered 1,2,...,N.

The second line of input will contain two integers S F, where S is the star at which you begin the race and F is the star at which you end the race (i.e., Alpha Centauri). You are guaranteed that 1 <= S,F <= N.

The third line of input will contain a single integer P representing the number of ordinary paths that you are allowed to take from star to star. Following this will be P lines each describing a single path. Each of these lines will contain three integers A B T, meaning that you are allowed to travel from star A to star B and that the journey will take you precisely T minutes. You are guaranteed that 1 <= A,B <= N, that A ≠ B and that 1 <= T <= 1000.

The next line of input will contain a single integer W representing the number of wormholes. Following this will be W lines each describing a single wormhole. Each of these lines will contain two integers A B, meaning that the wormhole moves you from star A to star B (and takes you back in time). You are guaranteed that 1 <= A,B <= N and that A ≠ B.

Note that all paths and wormholes are one-way. That is, if the input includes a path or wormhole from star A to star B, you cannot use that path or wormhole to move from star B to star A (though of course, some other path or wormhole from B to A might appear elsewhere in the input). You are guaranteed that no two paths or wormholes will take you from the same star A to the same star B, and that it is actually possible for you to eventually reach Alpha Centauri.

Output

Your program must write directly to standard output. Your output should consist of a single integer describing the earliest time at which you can arrive at Alpha Centauri.

Sample Input

$\includegraphics[scale=0.7]{chariot.eps}$

The following input represents the map illustrated above. Regular paths are marked by solid lines, and the wormhole is marked by a dotted line. The beginning of the race is at star 1 on the left, and the end of the race is at star 6 on the right.

Sample Output

Explanation

The shortest route using ordinary paths from start to finish is 1 -> 4 -> 3 -> 6, taking a total time of 8+6+10 = 24 minutes. However, if we make use of the wormhole then we can arrive at the finish earlier.

If we travel along the regular path 1 -> 4 -> 5, we arrive at star 5 at time 15. Travelling down the wormhole 5 -> 2 takes us back to time 7, and then we can finish our journey along the path 2 -> 3 -> 6, arriving at the final star at time 7+5+10 = 22.