Trong một thành phố hiện đại với những con đường nối liền các khu vực, bạn được giao nhiệm vụ tìm ra hành trình ngắn nhất từ điểm xuất phát đến đích. Thành phố được biểu diễn dưới dạng một đồ thị vô hướng gồm ~N~ đỉnh và ~M~ cạnh. Mỗi cạnh được mô tả bởi ba số nguyên ~u~, ~v~, ~w~, cho biết có một con đường hai chiều nối giữa đỉnh ~u~ và đỉnh ~v~ với trọng số ~w~. Ngoài ra, bạn còn nhận được hai số nguyên ~x~ và ~y~ chỉ định đỉnh xuất phát và đích. Nhiệm vụ của bạn là tính khoảng cách ngắn nhất từ đỉnh ~x~ đến đỉnh ~y~.

Input

• Dòng đầu chứa ~4~ số nguyên: ~N, M, x, y~ (với ~N \leq 1000, M < N×N~).
• ~M~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~u~, ~v~, ~w~ ~(w \leq 10^9)~.

Output

• In ra một số nguyên là khoảng cách ngắn nhất từ đỉnh ~x~ đến đỉnh ~y~ nếu có đường đi từ ~x~ đến ~y~, ngược là in ra ~-1~.

Sample Input

6 7 2 4
1 2 2
3 4 5
1 5 3
2 4 6
3 5 5
2 6 1
6 4 2

Sample Output

3