Phát biểu bài toán

Trong một mạng gồm ~ N ~ máy tính được đánh số từ 1 đến ~ N ~. Các máy tính được kết nối thông qua ~ M ~ kênh trực tiếp giữa các cặp máy tính. Mỗi kênh có một chi phí truyền thông nhất định.

Yêu cầu: Tính chi phí nhỏ nhất để truyền một bức thông điệp từ máy ~ S ~ đến máy ~ T ~.

Dữ liệu vào

1. 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 ~(1 \leq N \leq 10000, 1 \leq M \leq 100000)~:
   • ~ N ~: số lượng máy tính.
   • ~ M ~: số lượng kênh kết nối.
   • ~ S ~: chỉ số của máy tính nguồn.
   • ~ T ~: chỉ số của máy tính đích.
2. ~ M ~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~ D_i, C_i, G_i ~:
   • ~ D_i ~: chỉ số máy tính đầu của kênh.
   • ~ C_i ~: chỉ số máy tính cuối của kênh.
   • ~ G_i ~: chi phí truyền thông qua kênh kết nối này ~(0 \leq G_i \leq 30000)~.

Dữ liệu ra

• Ghi ra chi phí nhỏ nhất để truyền thông điệp từ ~ S ~ đến ~ T ~.

Ví dụ minh hoạ

Input

5 7 1 5
1 2 3
1 4 8
2 3 5
2 4 4
3 5 5
4 3 8
4 5 3

Output

10

Giải thích:

• Con đường ngắn nhất từ máy 1 đến máy 5 là: ~ 1 \to 2 \to 4 \to 5 ~ với tổng chi phí là ~ 3 + 4 + 3 = 10 ~.