P16987 [NWERC 2018] Date Pickup

Richard and Janet are going on their first date. Richard has offered to meet her at home with his bicycle, and Janet tells him she will call when she is ready in $10$ to $20$ minutes. But Richard is impatient; while he could wait at home, he might also leave early and travel around the neighbourhood to minimise the time it takes him to reach her once she calls. Given the directed graph representing the neighbourhood around Richard's and Janet's houses, Richard wants to devise a route around the neighbourhood, after an optional waiting period at his own house, which minimises the time that Janet has to wait in the worst case. He can travel for as long as he likes and visit each intersection as many times as he likes. Janet will call Richard as soon as she is ready, and at that point Richard will take the shortest path to her that he can. Richard does not know exactly when Janet will be ready, but he knows it will be somewhere between $a$ and $b$ minutes, not necessarily at a whole minute. If Richard is passing through an intersection at the exact same instant Janet calls, the call is considered to happen before he chooses what to do at the intersection. It could happen that Janet never has to wait for $w$ minutes, but might have to wait for $w-\epsilon$ minutes for arbitrarily small $\epsilon>0$; in this case, the worst case waiting time is still defined to be $w$.

The input consists of: - One line with two integers $a,b$ ($0\le a\le b\le 10^{12}$), indicating that Janet will be ready in at least $a$ minutes and at most $b$ minutes. - One line with two integers $n,m$ ($2\le n\le m\le 10^5$), the number of intersections and roads. - $m$ lines, each with three integers $u,v,t$ ($1\le u,v\le n$, $1\le t\le 10^6$), indicating a one-way road from $u$ to $v$ taking exactly $t$ minutes. Richard's house is at intersection $1$ and Janet's house is at intersection $n$. It is guaranteed that it is possible to travel from Richard's house to Janet's house, and that every intersection has at least one outgoing road.

Output the time Janet has to wait in the worst case assuming she will be ready in at least $a$ minutes and at most $b$ minutes and Richard plans his route optimally. It can be shown that the worst case waiting time is always an integer.