Một thành phố có nút giao thông và con đường hai chiều nối giữa chúng. Con đường thứ nối nút và , và mất thời gian để đi qua. Một công ty giao hàng cần tìm đường đi nhanh nhất (tổng thời gian di chuyển nhỏ nhất) từ kho hàng ở nút đến một khách hàng ở nút .
Dữ liệu:
Dòng đầu tiên chứa bốn số nguyên .
dòng tiếp theo, mỗi dòng chứa ba số nguyên mô tả một con đường.
Kết quả: Một số nguyên duy nhất là tổng thời gian nhỏ nhất để đi từ đến . Nếu không có đường đi, in ra -1.
Ví dụ:
Dữ liệu:
5 6 1 5
1 2 2
1 3 8
2 3 1
2 4 5
3 4 3
4 5 1
Kết quả:
7
Giải thích: Đường đi nhanh nhất là với tổng thời gian là .
