Matcom Online Grader

The year is 2115. The Interplanetary Commercial Planning Center (ICPC) is supported by the Autonomous Communication Ministry (ACM).

A commercial operation is performed executing transactions between connected ACM offices throughout the galaxy. The execution of a transaction between two connected ACM offices involves a non-negative tax whose value increases, or decreases, continuously as a linear function $A \times t + B$ of time $t$, where $t$ is a real number measured in minutes during the day ($0 \leq t \leq 24 \times 60$).

The total tax of a commercial operation performed between a source ACM office and a destination ACM office at some time $t$, is calculated as the minimum possible sum of the taxes of the executed transactions between the ACM offices visited along some path from the source ACM office to the destination ACM office. The tax of each transaction is calculated at the same time $t$.

Since the tax of the transactions between connected ACM offices is continually changing during the day, it would be better to perform the commercial operation at some specific time in the day, in order to maximize the collected tax. At that time, ACM decides to perform the commercial operation, and not before or after.

Your task is to write a program that receives as input the description of the ACM office network and returns as output the maximum total tax of the commercial operation that can be achieved during the day, that is, the maximum total tax that ACM can collect.

The first line contains two integers $N$ and $M$, representing respectively the number of ACM offices in the network, and the number of connections ($2 \leq N \leq 1000$ and $1 \leq M \leq 10^4$). The ACM offices are identified with distinct integers from $1$ to $N$, being $1$ the source ACM office and $N$ the destination ACM office. Each of the next $M$ lines describes a connection with four integers $I$, $J$, $A$ and $B$, indicating that there is a bidirectional connection between office $I$ and office $J$ ($1 \leq I \lt J \leq N$), such that the tax of a transaction executed between office $I$ and office $J$ at time $t$ is defined by the formula $A \times t + B$ ($−100 \leq A \leq 100$ and $0 \leq B \leq 10^6$). Taxes are non-negative, so $A \times t + B \geq 0$ for $0 \leq t \leq 24 \times 60$. There is at most one connection between each pair of ACM offices, and there is at least one path between the source ACM office and the destination ACM office.

Output a line with a rational number representing the maximum total tax that ACM can collect. The result must be output as a rational number with exactly five digits after the decimal point, rounded if necessary.