favorite We need a little bit of your help to keep things running, click on this banner to learn more

Buses and airplanes

Buses and airplanes

In Neverlyandii there are N cities between which travel by bus. Moreover, between some cities operating air traffic (flights).

Each flight (both bus and air) links the two cities (both sides). Between any two cities laid no more than one run of each type. The duration of each flight is known and is the same in both directions.

Flight Schedules perfect fit for the time, so that time spent on each component route (consisting of several runs) are simply the sum of durations of its constituent individual flights.

At the initial time you're in town A. Your job - as soon as possible to get into town B. Unfortunately, you have limited resources, so you can afford no more than M plane tickets (ie no more than M times can use flights).


The first line contains the numbers N, M, A, B, separated by spaces (A and B - number of initial and final cities, respectively) (1N1000, 0M10, 1AN, 1BN, AB).

The second line contains a V - the number of bus trips (1V20000). Each of the next V lines contain a description of a voyage in the following form:

IJK (after 1 space), where I and J - number of cities of this flight, K - its duration (in hours) (1IN, 1JN, IJ, 1K1000).

The next line contains a W - the number of flights (1W20000). Each of the next W lines contain a description of a flight (as well as for bus services).


The duration of the shortest route (in hours), or 0 if the B to get into town is impossible.

Time limit 2 seconds
Memory limit 256 MiB
Input example #1
4 1 1 4
1 2 20
2 3 10
3 4 5
1 3 25
2 1 3
2 4 2
3 4 1
Output example #1