27281번 - 운전병의 딜레마

원래 특별한 일정이 없던 간부님에게 급작스럽게 회의 일정이 잡혔다! 간부님의 운전병은 즉시 지도를 펼쳐 회의실의 위치를 살펴보았다.

지도에는 $N$개의 구역과 각 구역들을 양방향으로 연결하는 $M$개의 도로가 그려져 있으며, 각 도로에는 이동하는 데 걸리는 시간과, 도로의 불편도가 작성되어 있다. 운전병은 현재 $1$번 구역에 있으며, 회의실은 $N$번 구역에 있다.

회의 시간은 앞으로 $T$만큼 남았기 때문에, 반드시 시간 $T$ 안에 회의실에 도달하여야 한다. 또한, 갑작스럽게 잡힌 회의 일정인 만큼 간부님이 달리는 차 안에서 서류작업을 진행해야 하므로 회의실까지 가는 데 최대한 불편하지 않도록 운전해야만 한다. 이때, 회의실까지 가는 데 걸리는 시간은 이용한 도로의 걸리는 시간의 합이며, 간부님이 느끼는 불편도는 이용한 도로의 불편도의 최댓값이다.

운전병은 이미 운전의 귀재이기 때문에, 본인이 원하는 그 어떤 도로에서도 걸리는 시간을 $x>0$인 $x$만큼 늘려서 도로의 불편도를 $x$만큼 내릴 수 있다. 단, 도로의 불편도를 $0$ 미만으로 내릴 수는 없다. 하지만 불편도를 낮추기 위해 너무 천천히 달리면 시간 안에 회의실에 도달하지 못할 수도 있고, 그렇다고 계속 정속 주행을 하게 되면 간부님이 느끼는 불편도가 너무 높아진다는 딜레마에 빠지고 말았다!

운전병을 위해 $T$시간 안에 회의실로 갈 때 간부님이 느끼는 최소 불편도를 구해주자.

첫 번째 줄에 구역 개수 $N$과 도로 개수 $M$, 도달해야 하는 시간 $T$가 공백으로 구분되어 정수로 주어진다. $(2\leq N\leq 50\,000;$ $1\leq M\leq 100\,000;$ $1\leq T\leq 10^9)$

두 번째 줄부터 $M+1$번째 줄까지, $i$번째 도로가 연결하는 두 구역의 번호 $u_i, v_i$와 해당 도로를 이용하는 데 걸리는 시간과 불편도 $t_i, s_i$가 공백으로 구분되어 정수로 주어진다. $(1\leq u_i,v_i\leq N;$ $u_i\neq v_i;$ $1\leq t_i\leq 10^9;$ $0\leq s_i\leq 10^9)$

$T$시간 안에 회의실로 갈 때 간부님이 느끼는 최소 불편도를 출력한다.

만약 어떻게 해도 $T$시간 안에 회의실에 도달할 수 없다면, $-1$을 출력한다.