Mô tả và yêu cầu

Đường đi ngắn nhất
Cho đơn đồ thị vô hướng liên thông G = (V, E) gồm n đỉnh và m cạnh, các đỉnh được
đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m, và 2 đỉnh s, t.
Yêu cầu: Tìm đường đi ngắn nhất từ s đến t.
Dữ liệu: Vào từ file văn bản MINPATH.INP gồm
 Dòng 1: Chứa 4 số n, m, s, t (1 ≤ n ≤ 1000; 1 ≤ m ≤ 50000).
 m dòng tiếp theo: Dòng thứ i chứa ba số nguyên u, v, c. Trong đó u, v là chỉ số
hai đỉnh đầu mút của cạnh thứ i và c trọng số của cạnh đó (0 ≤ c ≤ 10000).
Kết quả ghi ra file văn bản MINPATH.OUT chứa số nguyên là độ dài đường đi ngắn
nhất.

Ví dụ

MINPATH.INP             MINPATH.OUT
                            3 3 1 3                 4
                            1 2 3
                            2 3 1
                            1 3 5