최소 비용 구하기

N개의 도시와 M개의 버스 노선이 있다. 도시 A에서 도시 B까지 가는 최소 비용을 구한다. 가중치는 0 이상이다.

다익스트라 알고리즘으로 풀 수 있다.

입력

첫째 줄에 도시 수 N이 주어진다.

둘째 줄에 버스 노선 수 M이 주어진다.

다음 M개 줄에 출발 도시, 도착 도시, 비용이 주어진다.

마지막 줄에 출발 도시 A와 도착 도시 B가 주어진다.

• 1 ≤ N ≤ 1,000
• 1 ≤ M ≤ 100,000
• 0 ≤ 비용 ≤ 100,000

출력

A에서 B까지의 최소 비용을 출력한다.

예제 입력 1

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

예제 출력 1

4