Cho một đồ thị vô hướng có ~n(1 \leq n \leq 2500)~ đỉnh và ~m(1 \leq m \leq 6200)~ cạnh, hãy tìm đường đi ngắn nhất từ ~s~ đến ~t~.

Input

• Dòng đầu tiên chứa bốn số nguyên ~n, m, s, t~ cách nhau bởi dấu cách.
• ~m~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương ~s_i, t_i, w_i (1 \leq w_i \leq 10^9)~ là cạnh từ ~s_i~ đến ~t_i~ có độ dài ~w_i~.

Output

Một số nguyên đại diện cho độ dài của con đường ngắn nhất từ ~s~ đến ~t~. Dữ liệu đảm bảo rằng tồn tại ít nhất một đường đi.

Sample

Input #1

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

Output #1

7