Buses and airplanes#668
In Neverland there are cities between which buses operate. Additionally, there is air traffic (flights) between some cities.
Each route (bus or air) connects two cities in both directions. There is no more than one route of each type between any pair of cities. The duration of each route is known and is the same in both directions.
The schedules are perfectly aligned in time, so the total time for any complex route (consisting of several segments) is simply the sum of the durations of the individual routes in that path.
Initially, you are in city . Your goal is to get to city as quickly as possible. Unfortunately, you are limited in resources, and can purchase at most plane tickets (that is, you can use at most flights).
The first line contains the numbers , , , , separated by spaces ( and are the numbers of the initial and destination cities, respectively) (1 \leq N \leq 1000, 0 \leq M \leq 10, 1 \leq A \leq N, 1 \leq B \leq N, A \neq B).
The second line contains – the number of bus routes (1 \leq V \leq 20000). Each of the next lines contains a description of one route in the form:
(separated by spaces), where and are the cities connected by this route, and is its duration (in hours) (1 \leq I \leq N, 1 \leq J \leq N, I \neq J, 1 \leq K \leq 1000).
The next line contains – the number of flights (1 \leq W \leq 20000). Each of the next lines contains a description of one flight (in the same format as for bus routes).
Print the duration (in hours) of the shortest possible route, or if it is impossible to reach city .
Example 1