Cho đồ thị vô hướng ~G~ gồm ~N~ đỉnh và ~M~ cạnh có trọng số không âm. Hãy tìm tổng độ dài đường đi ngắn nhất từ đỉnh ~S~ đến đỉnh ~T~ trong đồ thị đã cho.

Input

• Dòng đầu tiên chứa 4 số nguyên dương ~N, M, S, T~ — lần lượt là số đỉnh, số cạnh, đỉnh xuất phát và đỉnh đích của đồ thị ~(1 \leq N \leq 10^5,\quad 1 \leq M \leq 10^6)~

• Tiếp theo là ~M~ dòng, mỗi dòng gồm 3 số nguyên ~U, V, W~, cho biết có một cạnh có hướng từ đỉnh ~U~ đến đỉnh ~V~ với trọng số ~W~ ~(1 \leq U, V \leq N,\quad 0 \leq W \leq 30000)~.

Output

• In ra một số nguyên duy nhất — tổng độ dài của đường đi ngắn nhất từ đỉnh ~S~ đến đỉnh ~T~.

Ví dụ

Input

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

Output

15