여정

제치포스폴리타의 군대가 코스트로마 시에서 돔니노 마을로 행군하고 있다. 두 명의 헤트만 스테판과 콘스탄틴이 함께 군대를 이끈다.

스테판은 코스트로마 지방의 도로 지도를 구했고, 매일 밤 어떤 도로를 따라 군대를 한 마을에서 다른 마을로 이동시킨다. 콘스탄틴은 마을들 사이를 잇는 비밀 오솔길 지도를 미리 사 두었고, 매일 낮 그 오솔길 중 하나를 따라 행군을 이끈다. 행군을 시작하기 전, 그때 지휘를 맡은 헤트만은 안내인 이반 수사닌에게 경로를 묻는다.

모든 도로의 길이는 스테판의 지도에 적혀 있으므로, 스테판은 자신의 지도를 기준으로 각 마을에서 돔니노까지의 최단 거리를 알고 있다. 마찬가지로 콘스탄틴은 자신의 지도에 있는 오솔길을 따라 각 마을에서 돔니노까지의 최단 거리를 알고 있다.

이반 수사닌은 비밀 요원이라는 사실이 드러나기를 원하지 않는다. 그래서 매번, 묻는 헤트만의 지도를 기준으로 한 돔니노까지의 최단 거리가 항상 엄격하게 줄어들도록 도로(스테판이 물을 때)나 오솔길(콘스탄틴이 물을 때)을 고른다.

스테판의 지도	콘스탄틴의 지도	수사닌의 경로

이반이 돔니노까지 만들 수 있는 가장 긴 경로를 찾아라.

첫 번째 줄에는 세 정수 n, s, t가 주어진다. 각각 코스트로마 지방의 마을 수, 출발 마을, 돔니노 마을을 뜻한다 (2 ≤ n ≤ 1000; 1 ≤ s, t ≤ n). 마을은 1번부터 n번까지 번호가 매겨져 있다. 출발 마을과 돔니노는 서로 다르다.

이어서 두 개의 블록이 주어진다. 첫 번째 블록은 스테판의 지도를, 두 번째 블록은 콘스탄틴의 지도를 설명한다.

각 블록의 첫 번째 줄에는 정수 m이 주어지는데, 이는 마을들 사이의 도로/오솔길 수이다 (n − 1 ≤ m ≤ 100000). 이어지는 m개의 줄에는 각각 세 정수 a, b, l이 주어지며, 이는 마을 a와 b를 잇는 길이 l의 도로/오솔길을 뜻한다 (1 ≤ a, b ≤ n; 1 ≤ l ≤ 10^6).

군대는 도로나 오솔길을 양방향 어느 쪽으로든 이동할 수 있다. 각 지도에서 임의의 두 마을 사이를 오갈 수 있음이 보장된다. 군대는 저녁에 마을 s에서 출발하여, 매일 밤 도로 하나씩, 매일 낮 오솔길 하나씩 이동한다(따라서 첫 이동은 도로이다).

이반 수사닌이 군대가 돔니노에 도착하기 전까지 만들 수 있는 가장 긴 경로의 전체 길이(사용한 도로와 오솔길의 길이 합)를 출력하라. 만약 이반이 군대를 돔니노에 결코 도착시키지 않고 영원히 이동시킬 수 있다면 -1을 출력하라.