Cho đơn đồ thị có hướng ~G = (V,E)~ gồm ~n~ đỉnh và ~m~ cạnh có hướng và trọng số. Hãy cho biết độ dài đường đi ngắn nhất từ đỉnh ~l~ đến đỉnh ~r~.

Đảm bảo luôn tồn tại một đường đi từ ~l~ đến ~r~.

Input:

File DIJKSTRA.INP gồm:

• Dòng đầu tiên chứa bốn số nguyên ~n~, ~m~, ~l~, ~r~ ~(3 \le n,m \le 100;\ l,r \in [1;n])~.
• ~m~ dòng tiếp theo, mỗi dòng gồm 3 số nguyên ~u, v, w~ thể hiện đường đi có hướng từ đỉnh ~u~ đến đỉnh ~v~ và có trọng số ~w~ ~(w \le 100)~.

Output:

File DIJKSTRA.OUT gồm một số nguyên là độ dài đường đi ngắn nhất từ ~l~ đến ~r~.

Sample Input 1

7 10 1 7
1 2 4
1 3 5
1 4 2
2 5 10
3 5 12
3 6 6
4 5 4
4 6 10
5 7 14
6 7 2

Sample Output 1

13

Giải thích

Đường đi ngắn nhất từ nút ~1~ đến nút ~7~ là ~1-3-6-7~, với tổng chiều dài là ~13~.