Một công ty xây dựng đang lên kế hoạch xây dựng một cầu vượt tại một nút giao thông quan trọng trong thành phố. Để hoàn thành dự án, công ty cần vận chuyển vật liệu xây dựng (xi măng, thép, cát, đá,...) từ N nhà cung cấp đến địa điểm thi công.

Có M tuyến đường giao thông giữa các nhà cung cấp và công trường. Mỗi tuyến có:

• Chi phí vận chuyển (có thể bị ảnh hưởng bởi phí cầu đường, trợ cấp hoặc tắc nghẽn giao thông).

• Giới hạn tải trọng: Mỗi tuyến đường có một giới hạn về tải trọng tối đa của xe tải có thể đi qua.

Công ty cần tìm tuyến đường rẻ nhất để vận chuyển một khối lượng vật liệu X (tấn) từ nhà cung cấp chính (s) đến địa điểm thi công (t) mà không vi phạm giới hạn tải trọng của tuyến đường. Đồng thời thông báo nếu tồn tại chu trình âm.

Input:

Dòng đầu tiên chứa 5 số nguyên:

• n (1 ≤ n ≤ 1000) - Số đỉnh của đồ thị.

• m (1 ≤ m ≤ 10000) - Số cạnh của đồ thị.

• s (1 ≤ s ≤ n) - Đỉnh xuất phát (nhà cung cấp chính).

• t (1 ≤ t ≤ n) - Đỉnh đích (địa điểm thi công).

• X (1 ≤ X ≤ 10000) - Khối lượng vật liệu cần vận chuyển.

M dòng tiếp theo, mỗi dòng chứa 4 số nguyên:

• u, v (1 ≤ u, v ≤ n) - Cạnh có hướng từ u đến v.

• w (-10000 ≤ w ≤ 10000) - Chi phí vận chuyển trên cạnh đó.

• cap (1 ≤ cap ≤ 10000) - Giới hạn tải trọng của tuyến đường.

Output:

Dòng 1: 

• Nếu không có đường đi từ s đến t thỏa mãn điều kiện sức chứa ≥ X, in ra -1.

• Nếu phát hiện có chu trình âm, in ra "Chu trình âm tồn tại!".

• Nếu tồn tại đường đi ngắn nhất: In ra khoảng cách nhỏ nhất từ s đến t.

Dòng 2:

• Nếu tồn tại đường đi ngắn nhất: In ra đường đi từ s đến t theo thứ tự các đỉnh đi qua.