꼭 들러야 하는 곳

첫 줄에 노드의 수 n, 간선의 수 m (0 이상 4000 이하), 반드시 들러야 하는 노드 v 가 주어집니다. n 은 2 이상 100000 이하입니다. 이어서 m개의 줄에 방향 간선 u v w 가 주어집니다. u 에서 v 로 가는 비용이 w (1 이상 1000000 이하) 입니다.

1번에서 출발해 반드시 v 를 거쳐 n번에 도착하는 최단 거리를 출력하세요. 그렇게 갈 수 없으면 -1 을 출력합니다.

예시

입력

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

출력

4