406673: GYM102483 D 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 an impatient person; while he could wait at home for Janet's signal, he might also leave early and travel around the neighbourhood for a bit, in order to minimise the time it takes him to reach her once she calls. Due to his impatience, once Richard is on his bicycle, he does not want to ride any slower than the legal speed limit, stop at intersections, or wait outside Janet's house (but he does not mind passing by Janet's house and returning to it later).

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 in 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. For example, if he is passing by Janet's house at the moment she calls, he can immediately stop there and she does not have to wait for him at all.

It could happen that Janet never has to wait for $$$w$$$ minutes, but that she might have to wait for $$$w - \epsilon$$$ minutes for arbitrarily small $$$\epsilon > 0$$$, if she calls Richard at some inopportune moment (say, nanoseconds after he has left an intersection). In this case, we still define the worst-case waiting time 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 the number of roads in the neighbourhood. The intersections are numbered from $$$1$$$ to $$$n$$$.
• $$$m$$$ lines, each with three integers $$$u$$$, $$$v$$$ and $$$t$$$ ($$$1 \le u,v \le n$$$, $$$1 \le t \le 10^6$$$), indicating that there is a one-way road from intersection $$$u$$$ to intersection $$$v$$$, and that it takes Richard exactly $$$t$$$ minutes to travel along this road.

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 it is possible to exit each intersection through at least one road, even if that road just loops back to the same intersection.

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.

10 20
3 5
1 3 7
2 1 1
2 3 2
2 3 5
3 2 4

6

4 10
5 7
1 4 6
4 5 5
4 5 3
5 5 30
1 2 1
2 3 1
3 2 1

5