Đất nước Anpha có \(n\) thành phố được đánh số \(1, 2, 3, \ldots, n\). Giữa các thành phố này có \(m\) tuyến đường hai chiều đảm bảo kết nối giữa \(n\) thành phố. Mỗi tuyến đường thứ \(i\) (\(1 \leq i \leq m\)) được mô tả bởi cặp số \((u_i, v_i)\) kết nối trực tiếp hai thành phố \(u_i\) và \(v_i\) (\(u_i \neq v_i\)) và được gán hai số nguyên dương \(c_i\), \(d_i\), trong đó \(c_i\) là độ đẹp và \(d_i\) là chi phí phát sinh khi đi qua tuyến đường.

Giả sử \(s\) và \(t\) là hai thành phố của đất nước Anpha. Một công ty ABC đang cần vận chuyển một chuyến hàng có trọng lượng \(W\) từ thành phố \(s\) tới thành phố \(t\). Ta gọi một đường đi từ \(s\) đến \(t\) là một dãy \(z_0, z_1, z_2, \ldots, z_{k-1}, z_k\), trong đó \(z_0 = s\), \(z_k = t\), \((z_{i-1}, z_i)\) là tuyến đường với \(i = 1, 2, \ldots, k\). Chi phí cần vận chuyển một chuyến hàng có trọng lượng \(W\) từ thành phố \(s\) đến thành phố \(t\) theo đường đi nói trên là:

Trong đó \(d(z_{i-1}, z_i)\) là chi phí phát sinh của tuyến đường \((z_{i-1}, z_i)\), \(C_{min}\) là độ đẹp nhỏ nhất trong các tuyến đường trên đường đi mà xe hàng đi qua.

Yêu cầu: Cho trước hai thành phố \(s\) và \(t\). Hãy tìm đường đi để vận chuyển một chuyến hàng có trọng lượng \(W\) với chi phí nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m\) (\(2 \leq n \leq 150, 1 \leq m \leq 5000\)), mỗi số cách nhau một khoảng trắng.
• Dòng thứ hai chứa ba số nguyên dương \(s, t, W\) (\(1 \leq s, t \leq n\); \(1 \leq W \leq 10^4\)), mỗi số cách nhau một khoảng trắng.
• Dòng thứ \(i\) trong số \(m\) dòng tiếp theo chứa bốn số nguyên dương \(u_i, v_i, c_i, d_i\) mô tả thông tin về con đường thứ \(i\) (\(1 \leq u_i, v_i \leq n\); \(1 \leq c_i, d_i \leq 10000\), \(i = 1, 2, \ldots, m\)), mỗi số cách nhau một khoảng trắng.

Output

• Ghi một số duy nhất là chi phí nhỏ nhất để vận chuyển chuyến hàng (kết quả làm tròn đến hai chữ số sau dấu thập phân).

Example

4 5
1 3 8
1 2 1 1
1 3 1 4
1 4 2 3
3 4 5 2
3 2 1 2

9.00

Scoring

• Subtask 1 (40% số điểm): \(c_i = d_i = 1\) (\(\forall i = 1, 2, 3, \ldots, m\)).
• Subtask 2 (30% số điểm): \(c_i = 1\) (\(\forall i = 1, 2, 3, \ldots, m\)).
• Subtask 3 (20% số điểm): \(m = n - 1\).
• Subtask 4 (10% số điểm): Không có ràng buộc bổ sung.