Đất nước Anpha có ~n~ thành phố được đánh số ~1, 2, 3, \dots, 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 \le i \le n~) đượ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, \dots, z_k~, trong đó ~z_0 = s, z_k = t~, ~(z_{i-1}, z_i)~ là tuyến đường với ~i = 1, 2, \dots, 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à:

~d(z_0, z_1) + d(z_1, z_2) + \dots + d(z_{k-1}, z_k) + \frac{W}{C_{min}}~

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 \le n \le 150, 1 \le m \le 5000~).
• Dòng thứ hai chứa ba số nguyên dương ~s, t, W~ (~1 \le s, t \le n; 1 \le W \le 10^4~).
• 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~ (~1 \le u_i, v_i \le n; 1 \le c_i, d_i \le 10000~).

Output

• Ghi ra 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).

Sample Input 1

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

Sample Output 1

9.00