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ễ ~w~ 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 \cdot 10^5; M \le 3 \cdot 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

Ghi ra 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~.

Scoring

Sample Input 1

4 4 1 4
1 2 5 7
2 4 10 9
1 3 5 5
3 4 20 5

Sample Output 1

17

Notes

Gói tin có thể được truyền qua các trạm ~1 \rightarrow 2 \rightarrow 4~ qua các kênh ~1~ và ~2~.