은하 세금

2115년, 행성 간 상업 기획 센터(ICPC)는 자율 통신부(ACM)의 지원을 받는다.

상업 거래는 은하 곳곳에 있는 ACM 사무소 가운데 서로 연결된 두 곳 사이에서 실행된다. 연결된 두 사무소 사이에서 거래를 한 번 실행하면 세금이 붙고, 그 세금은 하루 중 시각 $t$의 일차식 $A \times t + B$에 따라 연속적으로 늘거나 줄어든다. $t$는 분을 단위로 하는 실수이고 $0 \le t \le 24 \times 60$이다. 세금은 절대 음수가 되지 않는다.

시각 $t$에 출발 사무소에서 목적 사무소까지 수행하는 상업 거래의 총세금은, 출발 사무소에서 목적 사무소로 가는 경로를 하나 골라 그 경로에서 실행되는 거래의 세금을 모두 더한 값 중 최솟값이다. 경로에 놓인 모든 거래의 세금은 같은 시각 $t$로 계산한다.

연결된 사무소 사이의 세금이 하루 내내 변하므로, ACM은 거두는 총세금이 가장 커지는 시각을 하나 골라 그 시각에만 상업 거래를 수행한다. 더 이르지도 늦지도 않게 딱 그때 수행한다.

ACM 사무소 연결망이 주어질 때, 하루 동안 ACM이 거둘 수 있는 총세금의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 사무소의 수 $N$과 연결의 수 $M$이 주어진다 ($2 \le N \le 1000$, $1 \le M \le 10^4$). 사무소에는 1번부터 $N$번까지 서로 다른 번호가 붙어 있고, 1번이 출발 사무소, $N$번이 목적 사무소이다.

다음 $M$개 줄에는 연결 하나를 나타내는 네 정수 $I$, $J$, $A$, $B$가 주어진다 ($1 \le I < J \le N$, $-100 \le A \le 100$, $0 \le B \le 10^6$). $I$번 사무소와 $J$번 사무소가 양방향으로 연결되어 있고, 시각 $t$에 두 사무소 사이에서 실행하는 거래의 세금은 $A \times t + B$이다. 세금은 음수가 되지 않으므로 $0 \le t \le 24 \times 60$인 모든 $t$에서 $A \times t + B \ge 0$이 성립한다. 같은 사무소 쌍을 잇는 연결은 많아야 하나이고, 출발 사무소에서 목적 사무소로 가는 경로는 적어도 하나 있다.

하루 동안 ACM이 거둘 수 있는 총세금의 최댓값을 한 줄에 출력한다. 소수점 아래 다섯째 자리까지, 다섯 자리를 모두 적는다. 그보다 아래 자리가 있으면 다섯째 자리에서 반올림한다.