18134번 - 치삼이의 대모험

치삼이네 동네에는 미로 같은 골목길이 가득 펼쳐져 있다. 교차점 i와 j사이의 골목길은 두 교차점 i와 j를 잇는다. 골목길을 통해 i에서 j로 이동할 수 있으며, j에서 i로 이동할 수도 있다. 치삼이는 현재 구구와 함께 집에 머무르고 있다.

골목길의 너머에 ‘전설의 치킨 삼겹살 세트’가 있다는 소문을 들은 치삼이는 치킨 삼겹살에 환장하는 구구를 위해 ‘전설의 치킨 삼겹살 세트’를 구해오기로 한다. '전설의 치킨 삼겹살 세트'를 구하기 위해서는 집에서 출발해 '전설의 치킨 삼겹살 세트'가 있는 교차점에 도달해 '전설의 치킨 삼겹살 세트'를 얻어 다시 집으로 돌아오는 여정이 필요하다. 하지만 연약한 치삼이가 지금 바로 모험을 떠나면 분명 모험을 하는 도중에 지쳐 쓰러지고 말 것이다. 따라서 치삼이는 모험을 하기 전에 혹독한 훈련을 거쳐 체력을 단련하기로 했다.

구구는 치삼이가 자신의 훈련 목표를 계산하기 쉽도록 골목길의 거리를 훈련을 위해 필요한 능력치로 나타낼 수 있는 새로운 단위를 만들었다. 따라서 골목길의 길이는 치삼이가 훈련해야 하는 훈련량과 일치한다. 치삼이는 강박증이 있어 집을 제외하고는 한 번 지나간 골목길과 교차점은 다시 지나지 않는다. 치삼이는 괴로운 지옥훈련을 최대한 적게 하고 싶어 한다. 치삼이가 구구에게 ‘전설의 치킨 삼겹살 세트’를 무사히 전해줄 수 있도록 치삼이가 무사히 모험을 마치고 돌아올 수 있는 최저 훈련량을 구해주자.

첫 번째 줄에 골목길의 교차점 개수 N(3 ≤ N ≤ 1,000)과 골목길의 개수 M(3 ≤ M ≤ 10,000)이 주어진다. 두 번째 줄부터 M개의 줄에 골목길의 정보가 주어진다. 각 줄에는 3개의 정수로 골목길의 거리 L(0 ≤ L ≤ 1,000), 골목길이 이어주는 두 개의 교차점 U, V(U≠V, 1 ≤ U, V ≤ N)이 주어진다. 교차점은 1부터 N까지의 자연수로 이름 붙여진다. 간선은 중복되게 주어지지 않는다. 마지막 줄에는 2개의 정수로 치삼이의 집의 위치 H와 '전설의 치킨 삼겹살 세트'가 있는 교차점의 위치 T(H≠T, 1 ≤ H, T ≤ N)가 주어진다.

치삼이가 무사히 모험을 마치고 돌아올 수 있는 최저 훈련량을 출력한다. 만일 도달하는 것이 불가능할 경우 -1을 출력한다.