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

ĐƯỜNG ĐI NGẮN NHẤT

Cho đồ thị có hướng gồm N đỉnh và M cung. Mỗi cung có một trọng số không âm.

Yêu cầu: Hãy tìm độ dài đường đi ngắn nhất từ đỉnh S đến đỉnh T.

Dữ liệu vào

o Dòng 1: Bốn số nguyên N, M, S, T (N ≤ 105, M ≤ 2 x 105).
o M dòng tiếp theo: Mỗi dòng gồm 3 số u, v, w mô tả cung từ u đến v có trọng số w
(w ≤ 109).

Kết quả: In ra độ dài đường đi ngắn nhất. Nếu không có đường đi, in -1.

Ví dụ

INPUT                                                OUTPUT
 3 3 1 3                                              15
 1 2 5
 2 3 10
 1 3 20