Một robot thám hiểm di chuyển qua \(N\) khoang nối nhau bằng \(M\) cửa chuyển tiếp một chiều. Khi đi qua cửa nối giữa khoang \(u\) và \(v\), robot có xác suất duy trì tín hiệu liên lạc thành công là \(p\) (\(0 < p \le 1.0\)). Xác suất liên lạc thành công trên toàn bộ hành trình là tích xác suất của các cửa nối đi qua.

Hãy tìm hành trình từ khoang \(S\) tới khoang \(T\) sao cho xác suất duy trì liên lạc thành công là lớn nhất.

Định dạng đầu vào

• Dòng đầu chứa bốn số nguyên \(N\), \(M\), \(S\), \(T\) (\(1 \le N \le 1000\), \(0 \le M \le 3000\), \(1 \le S, T \le N\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\), \(v\) (\(1 \le u, v \le N\)) và một số thực \(p\) (\(0.01 \le p \le 1.0\)), biểu thị xác suất thành công từ \(u\) sang \(v\).

Định dạng đầu ra

• In ra xác suất thành công lớn nhất làm tròn đúng 6 chữ số thập phân. Nếu không có hành trình nào, in ra 0.000000.

Ràng buộc

• Subtask 1 (40% số điểm): \(N \le 100\), \(M \le 200\).
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input:

3 3 1 3
1 2 0.9000
2 3 0.8000
1 3 0.7000

Output:

0.720000

Giải thích: Hành trình \(1 \to 2 \to 3\) có xác suất thành công lớn nhất: \(0.9 \times 0.8 = 0.72\) (hay \(0.720000\)).