출발지에서 목적지까지

첫 줄에 노드의 수 n, 간선의 수 m (0 이상 4000 이하), 출발 s, 도착 t 가 주어집니다. n 은 1 이상 100000 이하입니다. 이어서 m개의 줄에 방향 간선 u v w 가 주어집니다. 비용 w 는 1 이상 1000000 이하입니다.

s 에서 t 까지의 최단 거리를 출력하세요. 갈 수 없으면 -1 을 출력합니다.

예시

입력

4 5 1 4
1 2 1
1 3 5
2 3 2
2 4 7
3 4 1

출력

4