Driver's Dilemma

A meeting was suddenly scheduled for an officer who had no plans. The officer's driver immediately opened a map to find the location of the meeting room.

The map has $N$ districts and $M$ roads connecting them in both directions. Each road has a travel time and a discomfort value. The driver starts in district $1$, and the meeting room is in district $N$.

The meeting is $T$ away, so the driver must reach the meeting room within time $T$. The officer does paperwork in the car, so the driver must drive as smoothly as possible. The travel time to the meeting room is the sum of the travel times of the roads used. The discomfort the officer feels is the maximum discomfort among the roads used.

The driver can choose any road and lower its discomfort by $x$ by increasing its travel time by $x$, where $x>0$. Discomfort cannot go below $0$. Driving too slowly to lower discomfort may cause the driver to miss the deadline, while driving at normal speed keeps discomfort high.

Find the minimum discomfort the officer feels when reaching the meeting room within time $T$.

The first line contains $N$, $M$, and $T$ separated by spaces. ($2\leq N\leq 50\,000$, $1\leq M\leq 100\,000$, $1\leq T\leq 10^9$)

From the second line to the $(M+1)$-th line, the $i$-th line contains the two districts $u_i$ and $v_i$ that road $i$ connects, followed by its travel time $t_i$ and discomfort $s_i$, separated by spaces. ($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$)

Print the minimum discomfort the officer feels when reaching the meeting room within time $T$.

If the meeting room cannot be reached within time $T$ in any way, print $-1$.