13379 - DS_2021_HW4_Graph   

Description

You are the new miner of mine (礦坑). Today, the old miner teaches all new miners when an earthquake strikes, you have to exit the mine ASAP; Otherwise, you will be trapped and die. 

   

    There are two kinds of ways in the mine: bridge and tunnel, that are interconnected within the whole mine. Every bridge or tunnel has a length k. Since an earthquake damages the bridge structure, everyone is only allowed to go through one bridge when escaping, for safety issues. Given your current location in the mine and the exit, please help yourself find the shortest escaping path to the exit when the earthquake strikes. Please note that there might exist multiple tunnels/bridges between a  pair of locations.

 

For example, if we want to go from 1 (your current location) to 2 (the exit). 1 -> 2 with length 6 is one possible choice; Another choice is 1 -> 4 -> 2, with length 5. Please note that the length of 1 -> 4 -> 2 is not 2, because you can only go through one bridge in your escaping path.

 

Notice:

STL is allowed.

 

Input

The first line contains integers N, S, E.

 

N is the number of spots you would possibly visit in the mine.

S, E are the starting and exit spots, respectively.

 

The following line contains an integer T, the total number of the tunnels.

 

Then, we have T lines containing v, u, w, representing the tunnels connecting spots v and u with length w. You can go from v to u or u to v.

 

Then, there is a line containing an integer B, the total number of the bridges, and the following B lines contain v, u, w, which are the bridges connecting spots v and u with length w. You can go from v to u or u to v

 

Input ranges.

2 ≤ N ≤ 2000, 1 ≤ S, E ≤ N

T, B, v, u (1 ≤ T, B, v, u ≤ 20000)

w (1 ≤ w ≤ 100)

Output

Print the shortest length from S to E.

We guarantee the answer will not be greater than 4 x 10^9.

Sample Input  Download

Sample Output  Download

Tags




Discuss