Galactic Taxes

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

A commercial operation runs transactions between connected ACM offices across the galaxy. One transaction between two connected offices costs a tax that grows or shrinks continuously with the time of day, given by the linear function $A \times t + B$, where $t$ is a real number of minutes and $0 \le t \le 24 \times 60$. The tax is never negative.

The total tax of a commercial operation carried out at time $t$ between the source office and the destination office is the smallest possible sum of transaction taxes along a path from the source office to the destination office. Every transaction on that path is taxed at the same time $t$.

The taxes keep changing all day, so ACM picks the one moment that makes the collected total tax as large as possible and performs the commercial operation exactly then, not earlier and not later.

Given the network of ACM offices, print the largest total tax ACM can collect during the day.

The first line contains two integers $N$ and $M$, the number of ACM offices and the number of connections ($2 \le N \le 1000$, $1 \le M \le 10^4$). The offices carry distinct numbers from 1 to $N$. Office 1 is the source office and office $N$ is the destination office.

Each of the next $M$ lines describes one connection with four integers $I$, $J$, $A$, $B$ ($1 \le I < J \le N$, $-100 \le A \le 100$, $0 \le B \le 10^6$). Offices $I$ and $J$ are connected in both directions, and a transaction between them at time $t$ is taxed $A \times t + B$. Taxes are never negative, so $A \times t + B \ge 0$ holds for every $t$ with $0 \le t \le 24 \times 60$. At most one connection joins a given pair of offices, and at least one path runs from the source office to the destination office.

Print, on one line, the largest total tax ACM can collect during the day. Write exactly five digits after the decimal point. If the value has more digits, round half up at the fifth one.