우유 배송 경로

농부 존의 농장에는 외양간에서 우유 저장 탱크로 우유를 보내기 위한 낡은 파이프 네트워크가 있으며, 파이프는 총 $M$개 ($1 \le M \le 500$)입니다. 그는 내년에 대부분의 파이프를 교체하려 하지만, 외양간에서 저장 탱크까지 우유를 계속 보낼 수 있도록 정확히 하나의 경로에 해당하는 파이프만 그대로 남겨 두려고 합니다.

파이프 네트워크는 $N$개의 분기점 ($1 \le N \le 500$)으로 이루어져 있으며, 각 분기점은 여러 파이프의 끝점이 될 수 있습니다. 분기점 $1$은 외양간이고, 분기점 $N$은 저장 탱크입니다. $M$개의 파이프는 각각 두 분기점을 잇는 양방향 파이프이며, 지연 시간(우유가 파이프의 한쪽 끝에서 반대쪽 끝까지 도달하는 데 걸리는 시간)과 용량(정상 상태에서 단위 시간당 통과시킬 수 있는 우유의 양)을 가집니다. 같은 두 분기점을 잇는 파이프가 여러 개 존재할 수도 있습니다.

외양간에서 탱크로 이어지는 파이프 경로에 대해, 경로의 지연 시간은 그 경로에 포함된 파이프들의 지연 시간의 합이고, 경로의 용량은 그 경로에 포함된 파이프들의 용량 중 최솟값입니다(이 최소 용량이 전체 배송 속도를 제한하는 '병목'이기 때문입니다). 지연 시간이 $L$이고 용량이 $C$인 경로로 총 $X$ 단위의 우유를 보내는 데 걸리는 시간은 $L + X/C$입니다.

주어진 파이프 네트워크에서 $X$ 단위의 우유를 최소 시간에 보낼 수 있는, 외양간에서 저장 탱크까지의 단일 경로 하나를 선택했을 때의 최소 시간을 구하세요.

• 첫째 줄: 공백으로 구분된 세 정수 $N$, $M$, $X$ ($1 \le X \le 1{,}000{,}000$).
• 둘째 줄부터 $M$개의 줄: 각 줄은 하나의 파이프를 네 정수 $I$, $J$, $L$, $C$로 나타냅니다. $I$와 $J$ ($1 \le I, J \le N$)는 파이프 양 끝의 분기점이고, $L$과 $C$ ($1 \le L, C \le 1{,}000{,}000$)는 각각 그 파이프의 지연 시간과 용량입니다.

• 첫째 줄: 하나의 경로로 우유를 보내는 데 걸리는 최소 시간을 소수점 이하를 버려 정수로 출력합니다.

$X = 15$ 단위의 우유를 보낸다고 합시다. 분기점 $1$(외양간)과 분기점 $3$(탱크)을 직접 잇는 지연 시간 $14$, 용량 $1$짜리 파이프만 사용하면 $14 + 15/1 = 29$가 걸립니다. 반면 $1 \to 2 \to 3$ 경로는 지연 시간이 $10 + 10 = 20$, 용량이 $\min(3, 2) = 2$이므로 $20 + 15/2 = 27.5$가 걸려 더 유리합니다. 소수점 이하를 버리면 답은 $27$입니다.