eolymp
bolt
Try our new interface for solving problems
Problems

Buses and airplanes

Buses and airplanes

Time limit 2 seconds
Memory limit 256 MiB

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).

Input data

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).

Output data

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

Examples

Input example #1
4 1 1 4
4
1 2 20
2 3 10
3 4 5
1 3 25
3
2 1 3
2 4 2
3 4 1
Output example #1
18