호디티 흐리비마

Marin과 Vedran은 스슬로베니아를 가로지르는 여러 날짜의 여행에서 각각 스카우트 팀을 이끈다. 두 사람의 지도에는 $1$부터 $N$까지 번호가 붙은 $N$개의 마을이 있으며, 여기에 출발 마을 $s$와 목표 마을 $t$가 포함된다.

두 사람은 각자 따로 경로 지도를 준비했다. 각 지도는 마을을 정점, 길을 간선으로 하는 무방향 가중치 그래프다. 두 지도 모두 어느 마을에서든 다른 모든 마을로 갈 수 있다.

낮에는 Marin이 자신의 지도에 있는 길 하나를 골라 팀을 이끈다. 저녁에는 Vedran이 자신의 지도에 있는 길 하나를 골라 팀을 이끈다. 이 과정은 날마다 반복되며, 팀이 목표 마을 $t$에 도착하면 끝난다. 그 순간 누가 이끌고 있었는지는 상관없다.

Ivan은 두 사람을 골탕 먹이려는 사람이지만, Marin과 Vedran은 이를 모른다. 길을 고르기 전에 이끄는 사람은 Ivan에게 의견을 구하고, Ivan은 길을 하나 추천한다. 의심을 피하려면 Ivan이 고르는 길은 한 가지 조건을 만족해야 한다. 그 길을 따라간 뒤 목표 마을 $t$까지의 거리가 엄격히 줄어야 한다. 이때 거리는 그 순간 팀을 이끄는 사람의 지도만으로 계산한다.

아무도 의심하지 않는 상태에서 Ivan이 팀을 목표 마을 $t$까지 이끌 수 있는 최대 거리를 구하라. Ivan이 스슬로베니아 안을 영원히 이끌 수 있다면 -1을 출력하라.

탐험은 첫째 날 마을 $s$에서 시작하며, 처음 이끄는 사람은 Marin이다.

첫 줄에 $N$, $s$, $t$가 주어진다($2 \le N \le 1000$, $1 \le s, t \le N$).

이어서 Marin의 지도, Vedran의 지도 순서로 두 블록이 주어진다. 각 블록의 첫 줄에는 길의 수 $M$($N-1 \le M \le 10^5$)이 주어진다. 다음 $M$개 줄에는 자연수 $u$, $v$, $w$($1 \le u, v \le N$, $1 \le w \le 10^6$)가 주어지며, 이는 해당 지도에서 마을 $u$와 $v$ 사이에 길이 $w$인 길이 있다는 뜻이다.

Ivan이 팀을 이끌 수 있는 최대 거리를 첫 줄에 출력한다. 팀을 영원히 이끌 수 있다면 -1을 출력한다.

첫 번째 예시 설명: 첫째 날 Ivan은 Marin이 마을 1에서 마을 4로 팀을 이끌도록 한다. 저녁에는 Ivan이 Vedran에게 마을 4와 마을 2 사이의 길을 추천한다. 둘째 날 Ivan은 Marin이 마을 2에서 마을 3으로 이끌게 하고, 이어서 Vedran이 마을 3에서 마을 2로 이끌게 한다. 이후 매일 같은 방식을 반복할 수 있으므로 경로는 영원히 이어질 수 있다.

첫 번째 그림은 Marin의 지도, 두 번째 그림은 Vedran의 지도, 세 번째 그림은 Ivan이 세운 계획이다.