Journey

An army marches from the city of Kostroma to the village of Domino. Two generals, Stefan and Konstantin, lead it.

The generals carry different maps of the same region. The villages sit at the same places on both maps, but Stefan's map records only the main roads and Konstantin's map records only the narrow side paths. Walking a main road by day is dangerous, so the generals move the army like this. At night they follow one main road from Stefan's map, and by day they follow one side path from Konstantin's map.

A spy named Susanin marches with the army. He studies both maps and decides which road each general picks. His aim is to make the march to Domino as long as he can. Moving in a direction that has nothing to do with Domino would expose him, so Susanin only picks a road along which the shortest distance to the destination strictly decreases. The road he picks for Stefan must decrease the shortest distance to Domino measured with the main roads alone, and the road he picks for Konstantin must decrease the shortest distance to Domino measured with the side paths alone.

Find the length of the longest route Susanin can produce.

The first line contains the number of villages on the maps $n$, the number $s$ of the city of Kostroma where the march starts, and the number $t$ of the village of Domino where the march ends. ($2 \le n \le 1000$, $1 \le s, t \le n$, $s \ne t$) The villages are numbered from $1$ to $n$.

Two blocks follow in this order, one for Stefan's map and one for Konstantin's map.

The first line of each block contains the number of roads $m$. ($n-1 \le m \le 100000$)

Each of the next $m$ lines contains three natural numbers $a$, $b$, $l$. This means a bidirectional road of length $l$ joins village $a$ and village $b$. ($1 \le a, b \le n$, $1 \le l \le 1000000$) Several roads may join the same pair of villages, and a road whose $a$ equals its $b$ may appear.

Every village is connected on each map, so the roads of a single map already reach every village from every other village. The army starts at village $s$ and makes its first move at night, so the first map it uses is Stefan's map. After that it takes one main road each night and one side path each day.

Print the length of the longest route Susanin can produce before the army reaches Domino. The length of a route is the sum of the lengths of every main road and side path used along it. If Susanin can keep the army moving forever without ever reaching Domino, print -1.