시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 10 4 4 100.000%

문제

치삼이네 동네에는 미로 같은 골목길이 가득 펼쳐져 있다. 골목길의 너머에 ‘전설의 치킨삼겹살 세트’가 있다는 소문을 들은 치삼이는 치킨삼겹살에 환장하는 구구를 위해 ‘전설의 치킨삼겹살 세트’를 구해오기로 결심한다. 하지만 연약한 치삼이가 지금 바로 모혐을 떠나면 분명 모험을 하는 도중에 지쳐 쓰러지고 말 것이다. 따라서 치삼이는 모험을 하기 전에 혹독한 훈련을 거쳐 체력을 단련하기로 했다. 구구는 치삼이가 자신의 훈련 목표를 계산하기 쉽도록 골목길의 거리를 훈련을 위해 필요한 능력치로 나타낼 수 있는 새로운 단위를 만들었다. 따라서 골목길의 길이는 치삼이가 훈련해야 하는 훈련양과 일치한다. 치삼이는 강박증이 있어 집을 제외하고는 한 번 지나간 골목길과 교차점은 다시 지나지 않는다. 치삼이는 괴로운 지옥훈련을 최대한 적게 하고싶어 한다. 치삼이가 구구에게 ‘전설의 치킨삼겹살 세트’를 무사히 전해줄 수 있도록 치삼이가 무사히 모험을 마치고 돌아올 수 있는 최저 훈련량을 구해주자.

입력

첫번째 줄에 골목길의 교차점 개수 N(3 ≤ N ≤ 1,000)과 골목길의 개수 M(3 ≤ M ≤ 10,000)이 주어진다. 두번째 줄부터 M개의 줄에 골목길의 정보가 주어진다. 각 줄에는 3개의 정수로 골목길의 거리 L(0 ≤ L ≤ 1,000), 골목길이 잇는 두 개의 교차점 U, V(1 ≤ U, VN)이 주어진다. 교차점은 1부터 N까지의 자연수로 이름 붙여진다. 간선은 중복되게 주어지지 않는다. 마지막 줄에는 치삼이가 현재 위치한 교차점의 위치 H와 목적지 T(1 ≤ S, TN)가 주어진다.

출력

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

예제 입력 1

8 14
14 1 3
85 7 6
64 3 6
100 7 1
33 6 8
79 1 5
75 3 2
24 1 4
57 8 3
3 4 5
49 2 5
38 5 7
5 3 5
27 6 4
1 8

예제 출력 1

155

치삼이는 1번 정점에서 출발해 3번 정점을 거쳐 8번 정점에 도착해 치킨삼겹살을 가지고 6→4→1의 경로로 집으로 돌아온다.