The Waterloo campus is a huge utopia of information held in buildings. There are unidirectional pathways which connect buildings to each other, and one cannot travel unless they are on one of these paths. There may be multiple paths connecting two buildings. A common problem for your boss Calvin (who is at Waterloo) these days is that every time he sets foot outside there are annoying people who ask him questions about algorithms. In fact, in each pathway , there are classmates who are there to bother Calvin, for one minute each. Calvin, being a nice guy, must help each and every one of them. There is only one way to get out of talking to annoying classmates — a girlfriend! Luckily for Calvin, Cindy agreed to walk with him today, but only for one pathway (she's busy too!). Cindy is not willing to travel through the main pathways, which are too mainstream for her, but instead knows secret pathways that cannot be used unless she is there. Cindy therefore, has her own pathway set, consisting of different paths. Being the girlfriend, Cindy requires attention — for each pathway in her set, she needs to be attended to for minutes. Calvin wants to get from the computer science building (building ) to another computer science building (building ), and can choose to call Cindy to accompany him for any one pathway. Knowing this information, you would like to help your boss minimize the amount of time spent outside, with or without calling Cindy to walk with Calvin on one of the paths.
Line 1: 2 integers space separated:
Next lines: 3 integers space separated — , meaning that there is a unidirectional pathway from building to building , with coders to talk to.
Line : one integer,
Next lines: 3 integers space separated — , meaning that there is a unidirectional pathway from building to building , which Cindy and Calvin can take together for minutes.
Note: It is not guaranteed that Cindy's paths are unique from the normal paths.
One integer — the minimum time Calvin needs to travel from building to building , or
-1 if it is impossible to do so. It is guaranteed that the minimum time will always be less than or equal to .
4 3 1 2 5 2 3 5 3 4 5 2 1 3 7 2 4 3
Explanation of Output for Sample Input
There are many ways Calvin could've arrived at building from building . The fastest way is to get Calvin from in 5 minutes, and then call Cindy over to take Calvin through her secret passage from for a total of 8 minutes. Another possible (but slower) way is to call Cindy right away to have her walk with Calvin from in 7 minutes, and then go from for a total of 12 minutes.