10107 최소 비용 구하기 Gold V

문제

N개의 도시와 M개의 버스가 있다. 각 버스는 시작 도시, 도착 도시, 비용이 있다. A에서 B로 가는 최소 비용을 구하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000), 둘째 줄에 M (1 ≤ M ≤ 100,000)이 주어진다. 다음 M줄에 버스 정보가 주어진다. 마지막 줄에 A, B가 주어진다.

출력

최소 비용을 출력한다.

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

4