우유 생산 파이프

수현은 최근에 새로운 공장을 구입하여 그의 우유 생산 인프라를 확대했습니다. 새 공장은 인근 마을에 파이프 네트워크를 통해 연결되어 있으며, 수현은 공장에서 마을로 우유를 펌핑하기 위해 사용할 파이프 중 가장 좋은 세트를 고르는 방법을 알아내려고 합니다.

파이프 네트워크는 $N$ 개의 접점들 (파이프의 끝점들), 편리하게도 $1 \ldots N$ 까지 번호가 매겨져 있습니다. ($2 \leq N \leq 1000$). 접점 1은 수현의 공장을 표시하며, 접점 $N$ 은 마을입니다. 두 접점들을 연결하는 $M$ 개의 양방향 파이프가 있습니다.($1 \leq M \leq 1000$) $i$ 번째 파이프는 수현이 사용하기 위해 구입하는데 $c_i$ 달러가 들고, $f_i$ 리터의 우유를 초당 흐르게 할 수 있습니다.

수현은 접점 1과 $N$ 이 끝점인 한 개의 경로만 파이프를 구입하려고 합니다. 경로의 비용은 경로를 따라가는 파이프의 비용의 합입니다. 경로를 따라 가는 흐름의 속도는 경로를 따라 가는 파이프 중 가장 작은 흐름의 속도입니다. (이것은 경로를 따라가는 흐름의 병목 현상입니다). 수현은 흐름속도를 경로의 비용으로 나눈 값을 최대화하려고 합니다. $1$ 부터 $N$ 까지의 경로가 존재함이 보장됩니다.

입력의 첫 번째 줄에는 $N$ 과 $M$ 이 주어집니다. 이어지는 $M$ 줄 각각은 네 개의 정수로 파이프를 설명합니다: $a$ 와 $b$ (파이프로 연결된 두 접점), $c$ (비용), $f$ (흐름속도). 비용과 흐름속도는 모두 $1 \ldots 1000$ 범위의 양의 정수입니다.