시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB298743.750%

문제

nein나라는 이번에 sys나라를 바다를 통하여 침공을 할 계획이다. 둘 사이에는 여러 섬들이 있고, 이들 사이를 잇는 수로들이 있다. 하지만 nein나라와 sys나라사이의 바다는 파도가 매우 심하고, 수로마다 불규칙적이다. 수로마다 특정 파도 높이가 있는데, 이 수로를 통과하려면 그 높이에 비례하게 배의 두께를 두껍게 만들어야 한다. 만약, 특정 수로에 파도가 5라는 높이를 가진다면, 배의 두께는 5이상이어야 한다.

또한, 하나의 수로에 같은 시간에는 동시에 배가 지나갈 수 없다. 만약, 같은 섬에서 두 배가 있고 같은 수로를 사용하려 한다면, 1이라는 시간에 한 배가 출발하면, 다음 배는 2가 되어야 출발할 수 있다. 수로는 어느 곳이나 1이라는 시간에 통과할 수 있다. 그리고 배들은 수로를 이용하기 위하여 섬에 정박해 있다가 갈 수 있다.

이러한 수로들을 바탕으로 침공 계획을 세우고 있다. 전쟁은 속도가 생명이기 때문에, T라는 시간만에 k개의 배가 sys나라에 도착하여야 한다. 하지만 배가 동시에 도착할 필요는 없다. 또한, 배는 일괄적으로 만드므로 모두 두께가 동일하다.

이런 상황에서 nein나라가 sys나라를 T라는 시간만에 침공할 수 있는 배의 최소 두께를 구하시오.

입력

첫째 줄에는 nein나라와 sys나라 사이에 있는 섬들의 개수n, 섬들 사이의 수로의 개수 m, 침공을 위한 시간 T, 침공할 배의 개수 k가 주어진다. (2≤n≤50, 1≤t,k≤50, 1≤m≤1,000) nein나라는 1번섬, sys나라는 n번섬에 존재한다.

다음 m줄에는 수로의 두 섬 번호 a,b, 파도의 높이 h가 주어진다.(1≤a,b≤n, 1≤h≤100,000)

출력

nein나라가 sys나라를 T라는 시간만에 침공할 수 있는 배의 최소 두께를 구하시오. 만약 T라는 시간에 침공할 수 없다면 -1을 출력하시오.

예제 입력 1

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

예제 출력 1

2