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 là tìm đường đi ngắn nhất từ đỉnh s đến đỉnh t.

Định dạng đầu vào:

• Dòng đầu tiên: Bốn số nguyên phân cách bởi dấu cách: n, m, s, t:

  • n: Số lượng đỉnh (1 ≤ n ≤ 2500).
  • m: Số lượng cạnh (1 ≤ m ≤ 6000).
  • s: Đỉnh xuất phát (1 ≤ s ≤ n).
  • t: Đỉnh đích (1 ≤ t ≤ n).

• m dòng tiếp theo: Mỗi dòng gồm ba số nguyên uᵢ, vᵢ, wᵢ:

  • uᵢ, vᵢ: Hai đỉnh được nối bởi một cạnh.
  • wᵢ: Độ dài cạnh (1 ≤ wᵢ ≤ 10⁹).

Định dạng đầu ra:

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

Ví dụ

Input:

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

Output:

7