Journey

The army of the Rzeczpospolita is marching from the city of Kostroma to the village of Domnino. Two hetmans, Stefan and Konstantin, lead the army together.

Stefan obtained the road map of the Kostroma province, and every night he moves the army from one village to another along some road. Konstantin bought a map of the secret trails between villages in advance, and every day he leads the march along one of those trails. Before each march, the hetman in charge asks their guide, Ivan Susanin, for a route.

The length of every road is written on Stefan's map, so Stefan knows the minimum distance from each village to Domnino according to his map. In the same way, Konstantin knows the minimum distance from each village to Domnino along the trails on his map.

Ivan Susanin does not want to be exposed as a secret agent, so each time he picks a road (when Stefan asks) or a trail (when Konstantin asks) such that the minimum distance to Domnino, measured on the map of the hetman who is asking, strictly decreases.

Stefan's map	Konstantin's map	Susanin's route

Help Ivan find the longest possible route to Domnino.

The first line contains three integers n, s, and t — the number of villages in the Kostroma province, the starting village, and the Domnino village (2 ≤ n ≤ 1000; 1 ≤ s, t ≤ n). Villages are numbered from 1 to n. The starting village and Domnino are different.

Two blocks follow. The first describes Stefan's map, and the second describes Konstantin's map.

The first line of each block contains an integer m — the number of roads/trails between villages (n − 1 ≤ m ≤ 100000). Each of the next m lines contains three integers a, b, and l, describing a road/trail of length l between villages a and b (1 ≤ a, b ≤ n; 1 ≤ l ≤ 10^6).

The army may move in either direction along a road or a trail. It is guaranteed that on each map you can travel between any two villages. The army starts in the evening from village s and moves along one road each night and one trail each day (so the first move is a road).

Print the total length of the longest route that Ivan Susanin can arrange for the army before it reaches Domnino (adding up the lengths of the roads and trails used). If Ivan can keep the army moving forever without ever reaching Domnino, print -1.