Journey

The army of the Polish - Lithuanian Commonwealth is marching from the city of Kostroma to the village of Domnino. Leading the army are two hetmans, Stefan and Konstantin.

Stefan has acquired a map of the Kostroma region, and each night he leads the army from one village to another along one of the specified roads. Konstantin, on the other hand, has obtained a map of secret paths, and each day he leads the army along one of these paths. Before each march, each of the hetmans asks the guide, Ivan Susanin, which route is best to choose.

On Stefan’s map, the length of each road is indicated, so he knows the minimum distances between any village and the village of Domnino according to his map. Similarly, Konstantin knows the shortest distances to Domnino when following the paths on his map.

Ivan Susanin, being a secret agent, does not want to reveal his identity. Therefore, each time he selects a road (for Stefan) and a path (for Konstantin) so that the shortest distance to the village of Domnino, according to the map of the questioning hetman, strictly decreases.

Help Ivan find the longest possible route to the village of Domnino.

Input

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

Next follow two blocks, each describing a map: the first block is Stefan's map, and the second is Konstantin’s map.

The first line of each block contains an integer $m(n-1\le m\le 10^5)$ — the number of roads/paths between villages. Each of the following $m$ lines contains three integers $a,b$ and $l$, describing a road or path between villages $a$ and $b$ with a length of $l(1\le a,b\le n;1\le l\le 10^6)$.

The army can move in either direction along roads and paths. It is known that each hetman’s map allows one to reach any village from any other. The army starts in the evening from the starting village, advancing along one road each night and one path each day.

Output

Print the length of the longest route that Ivan Susanin can use to lead the army of the Polish–Lithuanian Commonwealth before they reach the village of Domnino (considering roads and paths). If Ivan can endlessly lead the army without reaching Domnino, print "$-1$".

Examples