P8017 [COCI 2013/2014 #4] UTRKA

Mirko and Slvako are taking part in a racing competition. The map for this competition has $N$ villages and $M$ roads. For the $i$-th road, there are two parameters $M_i$ and $S_i$, which represent the time Mirko and Slvako need to pass through this road, respectively. The race starts and ends at the same village. Now you need to find a route such that Mirko’s time on this route is as much better as possible than Slvako’s time on this route. In other words, let $X$ be the time Mirko needs to finish the route, and $Y$ be the time Slvako needs to finish the route. You need to find a route that uses as few villages as possible, and among those routes, makes $Y-X$ as large as possible.

The first line contains two positive integers $N$ and $M$, meaning there are $N$ villages and $M$ roads. The next $M$ lines each contain four positive integers $A_i, B_i, M_i, S_i$, meaning the $i$-th road connects village $A_i$ and village $B_i$. The time for Mirko to pass this road is $M_i$, and the time for Slvako to pass this road is $S_i$.

Output one line with two positive integers: the number of villages on the required route, and the value of $Y-X$ for the route that maximizes $Y-X$ among all routes with the minimum number of villages.

**Constraints** For $100\%$ of the testdata, $2 \le A_i, B_i \le N \le 300$, $A_i \ne B_i$, $2 \le M \le N \times (N-1)$, $0 \le M_i, S_i \le 10^6$. **Source** The score of this problem follows the original COCI settings, with a full score of $160$. This problem is translated from [COCI2013-2014 CONTEST #4](https://hsin.hr/coci/archive/2013_2014/contest4_tasks.pdf) _**T6 UTRKA**_. Translated by ChatGPT 5