Mô tả bài toán

Cho một đồ thị vô hướng với ~ n ~ đỉnh và ~ m ~ cạnh. Yêu cầu hãy tìm đường đi ngắn nhất từ đỉnh ~ s ~ đến đỉnh ~ t ~.

Input:

• Dòng đầu tiên chứa bốn số nguyên được phân tách bằng dấu cách ~ n, m, s, t ~.
• Sau ~ m ~ dòng, mỗi dòng gồm ba số nguyên dương ~ u, v, w ~ (~ w ~ là độ dài đường đi giữa ~ u ~ và ~ v ~).

Output:

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

Sample Input:

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

Sample Output:

7

Hint:

• ~ 1 \leq n \leq 2500 ~
• ~ 1 \leq m \leq 6000 ~
• ~ 1 \leq w_i \leq 10^9 ~