BubbleTeleport
It is year 2109 and 100th Bubble Cup is scheduled (it is indeed 100th, two were skipped in mid ‘70s during the Great Recession II). Perica takes part in all important programming competitions and of course he is a member of a team that is invited to Bubble Cup. But Perica has a bad habit, he really likes to sleep late in the mornings. He wants to be on time for the contest but he wants to leave his home as late as possible to get the most sleep. Perica always travels by train and uses Serbian Fast Railways Inc. He possesses a railway map and a train timetable so for every two connected stations he knows the distance between stations and departure and arrival times. Between any two stations there exists at least one direct or indirect path. Between two directly connected stations there exists only one train that goes back and forth in an infinite loop. If stations A and B are connected and the train needs time t to get from A to B, and we know from the timetable that the train departs station A at moment T, then the train is at station A at following moments in time: ... T - 4t, T - 2t, T + 2t, T + 4t... and also train is at station B at: ... T - 3t, T - t, T + t, T + 3t... We assume that the train travels at constant velocity and spends no time at stations. However, different trains may have different velocities.
Luckily for Perica, Serbian Fast Railways Inc. has just installed brand new teleport machines in every train and at every station. So even if he misses some train he still has a chance to teleport himself from the station into the train, but only if the train is close enough to the station. If two stations are closer to each other than the distance supported by teleport machines, Perica can teleport directly from one station to another without using the train. On the other hand, teleporting form train to station, from train to train and between non-connected stations is not possible. Help Perica find the fastest way from home to the contest.
Each of next m lines contains five integers: st1 st2 T t s, with 1 ≤ st1 , st2 ≤ n, -10000 ≤ T ≤ 10000, 0 < t, s ≤ 10000 where st1 and st2 are ordinal numbers of connected stations (enumeration starts with one), T is moment in time when train is at station st1 , t is time needed by train to travel between these two stations and s is distance between them.
Note 1: Starting and final station (home and contest location) are those with ordinal numbers 1 and n, respectively.
Note 2: All T's are relative to some moment in time (moment 0 when Perica arrives to starting station) and can take negative values
- Shortest time that Perica needs to get from home to the contest if he is at starting station at moment 0.
- Maximum amount of time that Perica can arrive late at the starting station so he still arrives at the final station at the same time as if he arrived at starting station at moment 0
Input:
4 4 1
1 2 0 5 2
1 3 0 7 2
2 4 4 5 2
3 4 6 2 2Output:
8 3 Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.