THỰC HÀNH

Trong một mạng gồm N máy tính đánh số từ 1 đến N. Sơ đồ nối mạng được cho bởi hệ thống gồm M kênh nối trực tiếp giữa một số cặp máy trong mạng. Biết chi phí truyền một đơn vị thông tin theo mỗi kênh nối của mạng.

Người ta cần chuyển một bức thông điệp từ máy S đến máy T sao cho tổng chi phí trên đường đi là nhỏ nhất.

Yêu cầu: Hãy lập trình để giải bài toán trên.

Dữ liệu: 

• Dòng đầu tiên ghi bốn số N, M, S, T cách nhau bởi dấu cách (N £ 10000, M £ 100000)
• Mỗi dòng thứ i trong số m dòng tiếp theo ghi thông tin về kênh nối thứ i của mạng gồm 3 số Di, Ci, Gi. Trong đó Di, Ci là chỉ số của hai máy tương ứng với kênh này và Gi (nguyên dương và £ 30000) là chi phí để truyền 1 đơn vị thông tin từ máy Di đến máy Ci (và ngược lại) theo kênh này (i=1,2,..n)

Kết quả: Ghi chi phí truyền thông điệp theo cách tìm được

Ví dụ:

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