Đường ống sữa

Mạng ống gồm $N$ điểm nối và $M$ ống hai chiều. Mỗi ống có độ trễ $L$ (thời gian sữa đi qua) và công suất $C$ (lưu lượng tối đa). Độ trễ của một đường đi = tổng $L$ các ống. Công suất = min $C$ các ống.

Cần bơm $X$ đơn vị sữa từ điểm $1$ đến điểm $N$ qua một đường đi. Thời gian = độ trễ + $X$/công suất.

Tìm đường đi có thời gian nhỏ nhất, làm tròn xuống.

Dữ liệu vào

• Dòng $1$: Ba số nguyên $N$, $M$, $X$ ($1\le N\le 500$, $1\le M\le 500$, $1\le X\le {10}^6$).
• $M$ dòng tiếp: Bốn số nguyên $I$, $J$, $L$, $C$ — ống nối $I$ và $J$ với độ trễ $L$ và công suất $C$ ($1\le L,C\le {10}^6$).

Dữ liệu ra

Một số nguyên — thời gian nhỏ nhất (làm tròn xuống).

Ràng buộc

• $1\le N\le 500$, $1\le M\le 500$, $1\le X\le {10}^6$
• $1\le L,C\le {10}^6$

Ví dụ