여정

어떤 나라의 군대가 Kostroma시에서 Domino마을로 이동한다. 두 장군 Stefan과 Konstantin이 이 군대를 이끈다.

두 장군은 같은 지역을 그린 서로 다른 지도를 들고 있다. 지도에 적힌 마을의 위치는 같지만, Stefan의 지도에는 큰 길만, Konstantin의 지도에는 좁은 샛길만 그려져 있다. 낮에 큰 길로 다니면 위험하므로 두 장군은 이렇게 군대를 움직인다. 밤에는 Stefan의 지도를 보고 큰 길 하나를 지나고, 낮에는 Konstantin의 지도를 보고 샛길 하나를 지난다.

군대에는 Susanin이라는 첩자가 섞여 있다. 그는 두 지도를 살펴보고 장군들이 어떤 길을 고르게 할지 정한다. Domino마을까지 가는 거리를 최대한 늘리는 것이 그의 목적이다. 그러나 Domino마을과 전혀 다른 방향으로 움직이면 첩자라는 의심을 산다. 그래서 Susanin은 각 지도에서 목적지까지의 최단거리가 반드시 줄어드는 길만 고른다. Stefan에게 고르게 하는 길은 큰 길만 이용했을 때 Domino마을까지의 최단거리가 줄어드는 길이어야 하고, Konstantin에게 고르게 하는 길은 샛길만 이용했을 때 Domino마을까지의 최단거리가 줄어드는 길이어야 한다.

Susanin이 만들 수 있는 가장 긴 경로의 길이를 구하시오.

첫째 줄에 지도에 있는 마을의 수 $n$, 행군을 시작하는 Kostroma시의 번호 $s$, 행군을 끝내는 Domino마을의 번호 $t$가 주어진다. ($2 \le n \le 1000$, $1 \le s, t \le n$, $s \ne t$) 마을에는 $1$번부터 $n$번까지 번호가 붙어 있다.

그 아래에 Stefan의 지도와 Konstantin의 지도를 나타내는 두 블록이 이 순서대로 주어진다.

각 블록의 첫째 줄에는 길의 개수 $m$이 주어진다. ($n-1 \le m \le 100000$)

이어지는 $m$개 줄에는 각각 세 자연수 $a$, $b$, $l$이 주어진다. $a$번 마을과 $b$번 마을을 잇는 길이 $l$짜리 양방향 길이 있다는 뜻이다. ($1 \le a, b \le n$, $1 \le l \le 1000000$) 같은 두 마을을 잇는 길이 여러 개 주어질 수 있고, $a$와 $b$가 같은 길도 주어질 수 있다.

각 지도에서 모든 마을이 서로 연결되어 있음이 보장된다. 즉 한 지도의 길만 이용해도 어느 마을에서 어느 마을로든 갈 수 있다. 군대는 $s$번 마을에서 출발하고 첫 이동을 밤에 하므로 처음 쓰는 지도는 Stefan의 지도이다. 그 뒤로는 밤마다 큰 길 하나, 낮마다 샛길 하나를 지난다.

Susanin이 Domino마을에 도착할 때까지 만들 수 있는 가장 긴 경로의 길이를 출력한다. 경로의 길이는 이동하며 지난 큰 길과 샛길의 길이를 모두 더한 값이다. Susanin이 군대를 Domino마을에 도착시키지 않고 영원히 움직일 수 있다면 -1을 출력한다.