Hôm nay, Tăng muốn bạn giúp anh ấy giải quyết bài toán sau. Tăng và người anh ấy thầm thương sống trong một vương quốc siêu lớn có tên là TINY. Trong vương quốc này, có ~N~ ngôi nhà được đánh số từ ~1~ đến ~N~, với nhà của Tăng là số ~X~ và nhà của người anh ấy thầm thương là số ~Y~. Họ đã đồng ý đi ra ngoài cùng nhau để thưởng thức cảnh sắc thiên nhiên rộng lớn của vương quốc TINY. Vương quốc đã xây dựng ~M~ con đường nối hai ngôi nhà, có nghĩa là có đường đi từ một ngôi nhà ~u~ qua ngôi nhà khác ~v~ và ngược lại. Thêm vào đó, các con đường này có chiều dài và thời gian đi lại là một số nguyên dương ~w~ không vượt quá một tỷ. Vì nhà của Tăng và nhà của người anh ấy thầm thương cách xa nhau, họ đã đồng ý gặp nhau ở một ngôi nhà khác sao cho thời gian đi đến đó hoặc thời gian để họ gặp nhau là tối thiểu, để họ có thể dành nhiều thời gian bên nhau hơn. Lưu ý: Tăng và người anh ấy thầm thương rời đi cùng một lúc.

Input

• Dòng đầu tiên chứa bốn số nguyên ~N, M, X, Y~.
• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~ và ~w~.

Output

• Một số nguyên duy nhất đại diện cho thời gian nhỏ nhất mà Tăng và người anh ấy thầm thương có thể gặp nhau. Nếu không tìm thấy ngôi nhà gặp nhau, xuất ~-1~.

Sample Input

7 7 1 7 
1 7 5 
1 3 1 
7 5 2 
3 5 3 
1 2 6 
1 6 10 
2 5 9

Sample Output

4

Notes

Bài toán có ~18~ bộ kiểm tra:

• ~10~ bộ đầu có ~N \leq 10^3~ và ~M \leq 10^4~.
• ~4~ bộ tiếp theo có ~N \leq 10^4~ và ~M \leq 10^5~.
• ~4~ bộ cuối có ~N \leq 10^5~ và ~M \leq 10^6~.