Hoditi Hribima

Marin and Vedran lead scout teams on a multi-day trip across Slovenia. Their maps show $N$ villages numbered from $1$ to $N$, including the start village $s$ and the target village $t$.

Each of them prepared a route map on their own. Each map is an undirected weighted graph where villages are vertices and paths are edges. In both maps, every village can reach every other village.

During the day, Marin leads the team along one path from his map. In the evening, Vedran leads the team along one path from his map. This repeats day after day until the team reaches the target village $t$, no matter who was leading at that moment.

Ivan secretly wants to cause trouble for them, but Marin and Vedran do not know this. Before each choice, the leader consults Ivan, who recommends a path. To avoid suspicion, the path Ivan picks must satisfy one condition: after walking it, the distance to the target village $t$ must decrease strictly. This distance is computed using only the map of the person leading the team at that moment.

Find the largest distance Ivan can lead the team to the target village $t$ without anyone becoming suspicious. If Ivan can lead the team forever across Slovenia, print -1.

The expedition starts on day one at village $s$, and Marin leads first.

The first line contains $N$, $s$, and $t$ ($2 \le N \le 1000$, $1 \le s, t \le N$).

Two blocks follow, first Marin's map, then Vedran's map. The first line of each block contains $M$ ($N - 1 \le M \le 10^5$), the number of paths. Each of the next $M$ lines contains three natural numbers $u$, $v$, and $w$ ($1 \le u, v \le N$, $1 \le w \le 10^6$), meaning that the map has a path of length $w$ between $u$ and $v$.

Print the maximum distance Ivan can lead the team, or -1 if the team can be led forever.

Explanation of the first sample: On day one, Ivan has Marin lead the team from village 1 to village 4. In the evening, Ivan recommends the path between 4 and 2 to Vedran. On day two, Ivan has Marin lead the team from village 2 to village 3, then has Vedran lead it from village 3 to village 2. The same can be repeated every following day, so the route can go on forever.

The first figure is Marin's map, the second is Vedran's map, and the third is the plan Ivan uses to lead them.