Date Pickup

Richard and Janet are going on their first date. Richard offered to meet her at home with his bicycle. Janet says she will call when she is ready, in 10 to 20 minutes. Richard is impatient. He can wait at home for her signal, or he can leave early and ride around the neighbourhood so that he reaches her as quickly as possible after she calls. Once he is on his bicycle, he will not ride slower than the legal speed limit, stop at intersections, or wait outside Janet's house. He does not mind passing by her house and coming back to it later.

The neighbourhood is a directed graph. Richard wants a route, after an optional wait at his own house, that minimizes the time 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 calls Richard as soon as she is ready, and then Richard takes the shortest path to her. Richard does not know exactly when she will be ready, only that it will be between $a$ and $b$ minutes, not necessarily a whole number of minutes.

If Richard passes an intersection at the exact instant Janet calls, the call counts as happening first, so he can choose his next move after hearing it. For example, if he is passing her house when she calls, he can stop there immediately and she does not wait.

Janet may never wait $w$ minutes, yet she may wait $w - \varepsilon$ minutes for an arbitrarily small $\varepsilon > 0$ if she calls at an unlucky moment, such as a few nanoseconds after Richard leaves an intersection. In that case the worst case waiting time is still $w$.

The first line has two integers $a$ and $b$ ($0 \le a \le b \le 10^{12}$), meaning Janet will be ready in at least $a$ minutes and at most $b$ minutes.

The second line has two integers $n$ and $m$ ($2 \le n \le m \le 10^5$), the number of intersections and the number of roads. Intersections are numbered from 1 to $n$.

Each of the next $m$ lines has three integers $u$, $v$, and $t$ ($1 \le u, v \le n$, $1 \le t \le 10^6$), meaning there is a one-way road from $u$ to $v$ that takes exactly $t$ minutes to travel.

Richard's house is intersection 1, and Janet's house is intersection $n$. Janet's house can be reached from Richard's house, and every intersection has at least one outgoing road, possibly a loop back to itself.

Print the worst case waiting time for Janet, given that she will be ready at some time between $a$ and $b$ minutes and Richard plans his route optimally.

The worst case waiting time is always an integer.