메이플 월드 라이딩 여행

메이플 월드는 $N$ 개의 마을로 구성되어 있다. 메이플 월드에서 라이딩을 타면, 비행 기능을 통해 현재 위치한 마을에서 출발해 일정 시간 후 다른 마을에 도착한다.

요정 웡키는 $M$ 종류의 라이딩을 가지고 있는데, $i$ 번 라이딩은 마을 $u_i$에서만 탈 수 있고 $t_i$ 초 후에 다른 마을 $v_i$에 도착한다.

요정 웡키는 마을 $S$에서 시작해 라이딩을 타고 서로 다른 마을을 여행하는 여행 계획을 세우려 한다. 이때, 여행 계획의 소요 시간은 라이딩을 타는 데 걸리는 시간의 총합이다.

요정 웡키는 여행 계획의 소요 시간이 너무 짧거나 긴 것을 원하지 않는다. 이를 위해 소요 시간이 $K$ 번째로 짧은 여행 계획의 소요 시간을 구하려 한다. 다시 말해, 가능한 모든 여행 계획을 소요 시간이 짧은 순으로 나열한 후 $K$ 번째 여행 계획의 소요 시간을 구하려 한다. 이때, 소요 시간이 같은 여행 계획은 임의의 순서로 나열한다.

예를 들어, 메이플 월드의 마을 $4$개와 라이딩 $6$종류가 <그림 1>과 같을 때, 마을 $1$에서 시작해서 소요 시간이 $4$번째로 짧은 여행 계획의 소요 시간을 구해보자.

<그림 2>와 같이 $8$가지 여행 계획이 가능하고, 소요 시간이 $4$번째로 짧은 여행계획의 소요 시간은 $5$초이다.

요정 웡키를 대신해서 서로 다른 마을을 방문하는 소요 시간이 $K$ 번째로 짧은 여행 계획이 존재하는지, 만약 존재한다면 그 여행 계획의 소요 시간을 출력하는 프로그램을 작성하여라.

입력 형식

첫 줄에 네 개의 정수 $N$, $M$, $K$, $S$가 공백으로 구분되어 주어진다. $(1 \le N, M, K \le 100\,000;$ $1 \le S \le N)$

이후 $M$ 개의 줄에 대해 $i$번 라이딩의 정보를 나타내는 세 개의 정수 $u_i$, $v_i$, $t_i$가 공백으로 구분되어 주어진다. $(1 \le u_i, v_i \le N;$ $1 \le t_i \le 1\,000\,000\,000)$

여기서, 모든 $i$에 대해 $u_i \ne v_i$이며, 모든 서로 다른 $i$, $j$ 쌍에 대해 $u_i \ne u_j$ 혹은 $v_i \neq v_j$이다. 또한, 마을 $S$에서 출발하여 도달할 수 없는 마을은 없다.

출력 형식

첫 줄에 소요 시간이 $K$ 번째로 짧은 여행 계획의 소요 시간을 출력한다.

만약 소요 시간이 $K$ 번째로 짧은 여행 계획이 존재하지 않는다면 -1을 출력한다.

예제

4 6 4 1
1 2 3
1 4 4
2 3 5
2 4 2
3 4 3
4 3 1

5

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설