함대

nein나라는 바다를 건너 sys나라를 침공하려고 한다. 두 나라 사이에는 섬이 여러 개 있고, 섬과 섬을 잇는 수로가 있다. 수로는 양방향으로 이용할 수 있다. 이 바다는 파도가 매우 거세고 파도 높이는 수로마다 다르다. 배가 어떤 수로를 지나가려면 배의 두께가 그 수로의 파도 높이 이상이어야 한다. 예를 들어 파도 높이가 5인 수로를 지나려면 배의 두께가 5 이상이어야 한다.

어느 수로든 통과하는 데 시간이 1 걸린다. 한 수로는 같은 시각에 배 한 척만 지나갈 수 있다. 예를 들어 같은 섬에 있는 두 배가 같은 수로를 이용하려 할 때, 한 배가 시각 1에 출발하면 다른 배는 시각 2가 되어야 출발할 수 있다. 배는 섬에 정박해 기다렸다가 나중에 수로를 이용할 수 있고, 한 섬에는 여러 배가 함께 머물 수 있다.

시각 0에 배 $k$척이 모두 nein나라가 있는 1번 섬에 있다. 전쟁은 속도가 생명이므로 시각 $T$까지 $k$척이 모두 sys나라가 있는 $n$번 섬에 도착해야 한다. 배가 동시에 도착할 필요는 없다. 배는 한꺼번에 만들기 때문에 모든 배의 두께가 같다.

nein나라가 시각 $T$까지 sys나라를 침공할 수 있는 배의 최소 두께를 구하시오.

첫째 줄에 섬의 개수 $n$, 수로의 개수 $m$, 침공에 쓸 수 있는 시간 $T$, 배의 개수 $k$가 주어진다. ($2 \le n \le 50$, $1 \le m \le 1{,}000$, $1 \le T, k \le 50$) nein나라는 1번 섬에, sys나라는 $n$번 섬에 있다.

다음 $m$개의 줄에는 수로가 잇는 두 섬의 번호 $a$, $b$와 그 수로의 파도 높이 $h$가 주어진다. ($1 \le a, b \le n$, $1 \le h \le 100{,}000$) 같은 두 섬을 잇는 수로가 여러 개 있을 수 있고, 각 수로는 따로 이용한다.

시각 $T$까지 배 $k$척이 모두 $n$번 섬에 도착할 수 있게 하는 배의 최소 두께를 출력한다. 두께와 관계없이 시각 $T$까지 침공할 수 없다면 -1을 출력한다.