운전병의 딜레마

원래 특별한 일정이 없던 간부님에게 갑자기 회의 일정이 잡혔다. 간부님의 운전병은 바로 지도를 펼쳐 회의실의 위치를 살폈다.

지도에는 $N$개의 구역과 각 구역을 양방향으로 잇는 $M$개의 도로가 그려져 있다. 각 도로에는 이동하는 데 걸리는 시간과 불편도가 적혀 있다. 운전병은 현재 $1$번 구역에 있고, 회의실은 $N$번 구역에 있다.

회의까지 남은 시간은 $T$이므로, 운전병은 반드시 시간 $T$ 안에 회의실에 도착해야 한다. 간부님은 차 안에서 서류 작업을 해야 하므로, 최대한 불편하지 않게 운전해야 한다. 회의실까지 걸리는 시간은 이용한 도로들의 시간의 합이고, 간부님이 느끼는 불편도는 이용한 도로들의 불편도 중 최댓값이다.

운전병은 원하는 도로에서, 걸리는 시간을 $x$만큼 늘리는 대신 불편도를 $x$만큼 낮출 수 있다. 단, $x>0$이며 불편도는 $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$을 출력한다.