Thành phố công nghệ Cyberland đang vận hành một hệ thống truyền tin đặc biệt gồm ~N~ trạm phát tín hiệu được đánh số từ ~1~ đến ~N~. Các trạm được kết nối với nhau bởi ~M~ kênh truyền tin hai chiều, kênh truyền tin thứ ~i~ (~1 \le i \le M~) kết nối hai trạm ~u_i, v_i~, có độ trễ truyền tải là ~w_i~ và tần số hoạt động là ~f_i~.

Để gửi một gói tin từ trạm nguồn ~S~ đến trạm đích ~T~ (~1 \le S, T \le N; S \ne T~), gói tin có thể đi qua một dãy các kênh truyền tin nối tiếp nhau. Tổng thời gian mà gói tin cần để đi từ ~S~ đến ~T~ được tính bằng tổng các yếu tố sau:

• Độ trễ đường truyền: Là tổng độ trễ của tất cả các kênh mà gói tin đi qua.
• Thời gian chuyển đổi tần số: Khi gói tin đi đến một trạm trung gian, nếu chuyển từ kênh có tần số ~f_x~ sang kênh có tần số ~f_y~ thì phải tốn thêm một khoảng thời gian bằng chênh lệch tần số giữa hai kênh, được tính bằng ~|f_x - f_y|~.

Yêu cầu: Biết rằng tại trạm nguồn ~S~ và trạm kết thúc ~T~ gói tin có thể ở bất kì tần số nào mà không tốn thêm thời gian chuyển đổi. Hãy tính thời gian ngắn nhất mà gói tin có thể được chuyển từ ~S~ đến ~T~.

Input

• Dòng đầu gồm bốn số nguyên dương ~N, M, S, T~ (~N \le 2 \times 10^5; M \le 3 \times 10^5~).
• ~M~ dòng tiếp theo, dòng thứ ~i~ gồm bốn số nguyên dương ~u_i, v_i, w_i, f_i~ mô tả một kênh truyền tin (~1 \le u_i, v_i \le N; u_i \ne v_i; 1 \le w_i, f_i \le 10^9~).

Output

• Một dòng chứa một số là thời gian ngắn nhất tìm được. Nếu không tồn tại đường đi từ ~S~ đến ~T~, ghi ra ~-1~.