The Waterloo campus is a huge utopia of information held in ~N~ buildings. There are ~M~ 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 ~i~, there are ~k_i~ 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 ~D~ different paths. Being the girlfriend, Cindy requires attention — for each pathway ~i~ in her set, she needs to be attended to for ~g_i~ minutes. Calvin wants to get from the computer science building (building ~1~) to another computer science building (building ~N~), 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.

Input Specification

Line 1: 2 integers space separated: ~N, M~ ~(2 \le N \le 500\,000, 1 \le M \le 500\,000)~

Next ~M~ lines: 3 integers space separated — ~a, b, k~, meaning that there is a unidirectional pathway from building ~a~ to building ~b~, with ~k~ coders to talk to. ~(1 \le a,b \le N, a \ne b, 0 \le k \le 10\,000)~

Line ~M+2~: one integer, ~D~ ~(0 \le D \le 500\,000)~

Next ~D~ lines: 3 integers space separated — ~a, b, g~, meaning that there is a unidirectional pathway from building ~a~ to building ~b~, which Cindy and Calvin can take together for ~g~ minutes. ~(1 \le a,b \le N, a \ne b, 0 \le g \le 10\,000)~

Note: It is not guaranteed that Cindy's paths are unique from the normal paths.

Output Specification

One integer — the minimum time Calvin needs to travel from building ~1~ to building ~N~, or -1 if it is impossible to do so. It is guaranteed that the minimum time will always be less than or equal to ~2^{30}~.

Sample Input

4 3
1 2 5
2 3 5
3 4 5
2
1 3 7
2 4 3

Sample Output

8

Explanation of Output for Sample Input

There are many ways Calvin could've arrived at building ~4~ from building ~1~. The fastest way is to get Calvin from ~1 \to 2~ in 5 minutes, and then call Cindy over to take Calvin through her secret passage from ~2 \to 4~ for a total of 8 minutes. Another possible (but slower) way is to call Cindy right away to have her walk with Calvin from ~1 \to 3~ in 7 minutes, and then go from ~3 \to 4~ for a total of 12 minutes.