Problem Description

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.

Input Format

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 Format

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.

3 4
1 2 3 0
2 3 3 0
3 1 0 100
2 1 0 4 

2 1

5 7
1 2 4 1
2 3 5 1
3 1 1 6
1 3 15 5
2 4 7 5
4 5 1 4
5 3 1 0 

5 2

Hint

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 T6 UTRKA.

Translated by ChatGPT 5