Journey#2267
The army of the Polish–Lithuanian Commonwealth is marching from the city of Lutenburg to the village of Feldheim. The army is led by two hetmans — Stefan and Konstantin.
Stefan has a map of the Lutenburg region indicating all the roads between villages. Each night, he leads the army from one village to another along one of these roads. Konstantin, on the other hand, has obtained a map of secret trails, and during the day he leads the army along one of these trails. Before each movement, both hetmans ask the guide Jan Mazur which route should be chosen.
Stefan's map shows the length of each road, so he can determine the shortest distance from any village to Feldheim by his map. Similarly, Konstantin knows the shortest paths according to his map of trails.
Jan Mazur, being a secret agent, tries not to arouse suspicion. Therefore, each time he selects a road (for Stefan) and a trail (for Konstantin) such that the shortest distance to the village of Feldheim according to the respective map strictly decreases.
Help Jan determine the maximum possible length of the route to the village of Feldheim.
The first line contains three integers , , and t~(2 \le n \le 1000, 1 \le s, t \le n) — the number of villages in the Lutenburg region, the starting village number, and the village number of Feldheim, respectively. Villages are numbered from to . It is guaranteed that s \ne t.
Then follow two blocks, each describing a map: the first block is Stefan's map, the second is Konstantin's.
The first line of each block contains an integer m~(n - 1 \le m \le 10^5) — the number of roads or trails. Each of the next lines contains three integers , , and l~(1 \le a, b \le n; 1 \le l \le 10^6) describing a connection between villages and of length .
It is allowed to move along roads and trails in both directions. For each map, it is possible to travel between any pair of villages. The army starts moving in the evening from the village , traveling one road per night and one trail per day.
Print a single integer — the maximum possible length of the route to the village of Feldheim (considering the alternating use of roads and trails). If Jan Mazur can lead the army indefinitely without ever reaching Feldheim, print -1.
Example 1
Example 2