405213: GYM101845 J Jinping Trains

Metr Pitrichev attended the 2018 ACM-ICPC World Finals in Beijing, China. Now that he finished streaming the contest he wants to travel from Beijing to Shanghai by train (he likes trains).

There are n (2 ≤ n ≤ 500) train stations in China and there are m (n - 1 ≤ m ≤ 500) train routes. Each train route consist of:

• u (1 ≤ u ≤ n): Station where the train starts.
• v (1 ≤ v ≤ n, v ≠ u): Station where train goes.
• t (1 ≤ t ≤ 1000): Number of minutes it takes the train to go from station u to station v. So, if the train departs from u at minute x, it will arrive to v at minute x + t.
• c (1 ≤ c ≤ 1000): Cost of taking the train (In RMB, the Chinese currency).
• f (1 ≤ f ≤ 10): Frecuency of the train, in minutes.
• s (0 ≤ s < f): Minute in which the first train leaves, so a trains leaves at each of these minutes: s, s + f, s + 2f, ...

In order for Metr to take a train that leaves at time x that goes from station a to station b, he must have been in station a at time x - 1.

Beijing railway station is station number 1 and Shanghai railway station is station number n. Metr arrived at Beijing railway station at time 0. Being very smart, Metr will take best route and arrive to Shanghai as early as possible and if there are multiple ways to arrive as early as possible he will spend as little money as possible. There is always at least one way to go from station 1 to station n.

The first line of input contains two integers n and m.

Each of the following m lines describes a train route with 6 space separated integers: u, v, t, c, f and s.

Print one line with two integers separated by a single space - the time Metr reaches his destination and the total cost of the trip (In RMB), respectively.

4 5
1 2 1 3 5 0
2 4 5 4 5 0
1 3 1 5 5 0
1 3 2 4 10 1
3 4 5 8 5 0

10 12

In the example:

• If Meter takes the first route and then the second route, he will arrive in 15 minutes and spend 7 RMB.
• If Meter takes the third route and then the fifth route, he will arrive in 15 minutes and spend 13 RMB.
• If Meter takes the fourth route and then the fifth route, he will arrive in 10 mitues and spend 12 RMB.