우유 펌프질

농부 존은 우유 생산 규모를 늘리기 위해 새 농장을 샀다. 새 농장은 인근 마을과 파이프망으로 연결되어 있고, FJ는 농장에서 마을로 우유를 퍼 올리는 데 쓸 파이프를 어떤 집합으로 사야 가장 좋은지 알아내려 한다.

파이프망은 $N$개의 접합점(파이프의 끝점)으로 표현되며, 편의상 $1 \ldots N$으로 번호가 붙어 있다($2 \leq N \leq 1000$). 접합점 1은 FJ의 농장이고 접합점 $N$은 마을이다. $M$개의 양방향 파이프가 있으며($1 \leq M \leq 1000$), 각 파이프는 두 접합점을 연결한다. $i$번째 파이프를 사는 데 드는 비용은 $c\_i$달러이고, 이 파이프는 초당 $f\_i$리터의 우유 유속을 감당할 수 있다.

FJ는 양 끝점이 접합점 1과 $N$인 경로 하나에 해당하는 파이프만 사려 한다. 경로의 비용은 경로 위 파이프들의 비용 합이다. 경로의 유속은 경로 위 파이프들의 유속 중 최솟값이다(경로를 따라 흐르는 유량의 병목이 되기 때문이다). FJ는 경로의 유속을 경로의 비용으로 나눈 값을 최대화하려 한다. $1$에서 $N$으로 가는 경로가 존재함은 보장된다.

첫 줄에 $N$과 $M$이 주어진다. 이어지는 $M$개의 줄 각각은 파이프 하나를 나타내는 네 정수 $a$, $b$, $c$, $f$로 이루어진다. $a$와 $b$는 파이프가 연결하는 서로 다른 두 접합점이고, $c$는 비용, $f$는 유속이다. 비용과 유속은 모두 $1 \ldots 1000$ 범위의 양의 정수이다.

최적 해의 값에 $10^6$을 곱한 값을 정수로 버림하여 출력한다(그 수가 정수가 아니면 그보다 작은 정수로 내림한다).

$1$에서 $N$으로 가는 경로가 하나뿐인 예이다. 이 경로의 유속은 $\min(3,4)=3$이고 비용은 $2+5=7$이다.