Trang trại của Farmer John có một mạng lưới cũ gồm \(M\) đường ống (\(1 \le M \le 500\)) để bơm sữa từ chuồng đến bể chứa sữa. Trong năm tới, ông muốn dỡ bỏ và nâng cấp phần lớn số đường ống này, nhưng vẫn muốn giữ nguyên các đường ống thuộc đúng một đường đi để tiếp tục bơm sữa từ chuồng đến bể chứa.

Mạng lưới đường ống được mô tả bởi \(N\) điểm nối (\(1 \le N \le 500\)), mỗi điểm có thể là đầu mút của một tập hợp các đường ống. Điểm nối \(1\) là chuồng, còn điểm nối \(N\) là bể chứa. Mỗi đường ống trong số \(M\) đường ống hai chiều nối một cặp điểm nối, đồng thời có một độ trễ (lượng thời gian để sữa đi từ đầu này đến đầu kia của đường ống) và một dung lượng (lượng sữa trên mỗi đơn vị thời gian có thể được bơm ổn định qua đường ống). Có thể có nhiều đường ống nối cùng một cặp điểm nối.

Đối với một đường đi gồm các đường ống nối từ chuồng đến bể, độ trễ của đường đi là tổng độ trễ của các đường ống trên đó, còn dung lượng của đường đi là giá trị nhỏ nhất trong các dung lượng của các đường ống trên đó (vì đây là "nút thắt cổ chai" giới hạn tốc độ tổng thể mà sữa có thể được bơm qua đường đi). Nếu FJ muốn gửi tổng cộng \(X\) đơn vị sữa qua một đường đi có độ trễ \(L\) và dung lượng \(C\), thời gian cần thiết vì thế là \(L + X/C\).

Với cấu trúc mạng lưới đường ống của FJ, hãy giúp ông chọn một đường đi duy nhất từ chuồng đến bể chứa sao cho có thể bơm \(X\) đơn vị sữa trong tổng thời gian nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(X\), cách nhau bởi dấu cách (\(1 \le X \le 1\,000\,000\)).
• \(M\) dòng tiếp theo, mỗi dòng mô tả một đường ống bằng bốn số nguyên \(I\), \(J\), \(L\), \(C\). \(I\) và \(J\) (\(1 \le I, J \le N\)) là các điểm nối ở hai đầu đường ống. \(L\) và \(C\) (\(1 \le L, C \le 1\,000\,000\)) lần lượt là độ trễ và dung lượng của đường ống.

Dữ liệu ra

In ra lượng thời gian nhỏ nhất để FJ gửi sữa dọc theo một đường đi duy nhất, làm tròn xuống số nguyên gần nhất.

Ví dụ

3 3 15
1 2 10 3
3 2 10 2
1 3 14 1

27

Nguồn

USACO 2012 December Contest, Silver — Problem 3: Milk Routing

Tác giả đề: Brian Dean, 2012.