연료 보급

보급장교 태승이는 연료를 부두에서 유류 저장고로 펌핑하기 위한 M개의 파이프 (1 <= M <= 500) 네트워크를 관리하고 있습니다. 그는 내년에 대부분의 파이프를 철거할 예정입니다. 다만, 여전히 부두에서 유류 저장고로 연료를 펌핑할 수 있도록 오직 하나의 파이프만 그대로 두려고 합니다.

파이프 네트워크는 N개의 연결점 (1 <= N <= 500)에 의해 구성되어 있으며, 각각은 파이프의 시점과 종점일 수 있습니다. 연결점 1은 부두이고, 연결점 N은 유류 저장고입니다. M 개의 양방향 파이프는 관련된 펌핑 시간 (연료가 파이프의 한쪽 끝에서 다른 쪽 끝까지 도달하는 데 걸리는 시간) 및 용량 (파이프를 통해 펌핑될 수 있는 단위 시간당 연료의 양)이 있습니다. 여러 파이프는 동일한 한 쌍의 연결점 사이를 연결할 수 있습니다.

부두에서 유류 저장고로 이어지는 파이프의 경우, 대기 시간은 경로를 따른 파이프의 대기 시간의 합이며, 용량은 경로를 따른 파이프의 용량의 최솟값입니다 (이것은 연료가 파이프를 통해 펌핑될 수 있는 총 속도를 제한하는 '병목현상'입니다). 태승이가 대기 시간이 L이고 용량이 C인 파이프 경로를 통해 총 X 단위의 연료를 보내려는 경우, 소요시간은 L + X/C입니다.

파이프 네트워크 구조를 고려할 때, 최소한의 총 시간 안에 X 단위의 연료를 펌핑할 수 있도록 부두에서 유류 저장고로 이어지는 단일 경로를 선택하는 데 도움을 주십시오.

• 1번째 줄 : 세 개의 공백으로 구분된 정수 : N M X (1 <= X <= 1,000,000).
• 2번째 줄..1+M번째 줄 : 각 라인은 4개의 정수를 사용하여 파이프를 설명합니다 : I J L C. I와 J (1 <= I, J <= N)는 파이프의 양 끝에 있는 연결점들입니다. L과 C (1 <= L, C <= 1,000,000)는 파이프의 대기시간과 용량을 제공합니다.

• 1번째 줄 : 태승이가 단일 경로를 따라 연료를 보내는 데 걸리는 최소 시간, 가장 가까운 정수로 반올림합니다.