고대 기록 보관소에는 1부터 N까지 번호가 붙은 N개의 기억 조각이 보관되어 있다.

각 기억 조각은 서로 다른 파형을 가지고 있으며, 복원기는 주어진 변환 카드들을 순서대로 사용해 한 파형을 다른 파형으로 바꿀 수 있다.

변환 카드는 모두 M개이다.

하나의 카드는 정해진 번호의 기억 조각에서만 사용할 수 있고, 사용하면 지정된 다른 번호의 기억 조각으로 파형이 바뀐다.

카드를 한 번 사용할 때마다 정해진 양의 에너지가 소모되며, 여러 장의 카드를 이어서 사용할 경우 소모 에너지는 모두 합산된다.

연구자는 A번 기억 조각의 파형을 출발점으로 삼아 B번 기억 조각의 파형을 얻으려고 한다.

가능한 변환 과정들 중에서 필요한 에너지 총합의 최솟값을 구하라.

입력은 A번 파형에서 B번 파형을 얻는 과정이 적어도 하나 존재하도록 주어진다.

입력

첫째 줄에 기억 조각의 개수 N(1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에 변환 카드의 개수 M(1 ≤ M ≤ 100,000)이 주어진다.

다음 M개의 줄에는 각 변환 카드를 나타내는 세 정수 u, v, e가 주어진다.

이는 u번 기억 조각의 파형에서 v번 기억 조각의 파형으로 바꿀 수 있으며, 이때 e만큼의 에너지가 소모된다는 뜻이다. e는 0 이상 100,000 미만의 정수이다.

마지막 줄에는 처음 파형의 번호 A와 얻어야 할 파형의 번호 B가 주어진다. 모든 번호는 1 이상 N 이하이다.

출력

A번 기억 조각의 파형에서 B번 기억 조각의 파형을 얻는 데 필요한 에너지 총합의 최솟값을 첫째 줄에 출력한다.

예제 입력 1

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

예제 출력 1

4