Hệ thống giao thông công cộng nơi Vinh ở gồm ga xe buýt, các ga được đánh số thứ tự từ đến . Có tuyến đường hai chiều nối giữa các cặp ga. Tuyến đường thứ nối trực tiếp cặp ga và , chi phí di chuyển trên tuyến đường này là . Mỗi cặp ga chỉ có nhiều nhất một tuyến đường nối chúng. Nhà Vinh ở gần ga và trường học ở gần ga . Hằng ngày đến trường Vinh đi bộ đến ga rồi lên xe buýt để đi đến ga . Khi đến ga , Vinh sẽ đi bộ đến trường. Vinh đã mua vé tháng cho đường đi từ ga đến ga với tổng chi phí trên các tuyến đường thuộc đường đi đó là nhỏ nhất. Sáng chủ nhật hàng tuần, Vinh có sở thích đến thư viện để đọc sách. Nhà Vinh cũng ở gần ga và thư viện ở gần ga . Để đến thư viện, Vinh đi bộ đến ga rồi đi xe buýt để đến ga , sau đó đi bộ đến thư viện. Để khuyến khích học sinh đến thư viện đọc sách, Ban quản lý ga xe buýt sẽ không thu phí khi đi trên các tuyến đường mà học sinh đó đã mua vé tháng. Nghĩa là, khi Vinh đi từ ga đến ga , nếu Vinh đi trên các tuyến đường thuộc đường đi từ ga đến ga mà Vinh đã mua vé tháng thì sẽ không mất phí, các tuyến đường không thuộc sẽ bị mất phí.
Yêu cầu: Bạn hãy tính xem, Vinh có thể chọn đường đi nào để đi từ ga đến ga (tất nhiên đường đi từ đến có tổng chi phí ít nhất) mà khi đi từ ga đến ga mất tổng chi phí là nhỏ nhất.
Dữ liệu gồm:
- Dòng đầu ghi hai số nguyên dương và số ga xe buýt và số tuyến đường nối trực tiếp giữa hai ga (.
- Dòng thứ hai ghi hai số và .
- Dòng thứ ba ghi hai số và .
- Dòng thứ trong dòng cuối, ghi ba số nguyên dương mô tả tuyến đường nối trực tiếp ga và ga với chi phí là .</li>
Kết quả:
- Tổng chi phí ít nhất mà Vinh có thể đi từ ga đến ga .
Ví dụ:
Input
Copy
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
Out
Copy
2
Giải thích
- Vinh sẽ mua vé theo đường đi: 1 → 2 → 3 → 5 → 6 (có tổng chi phí nhỏ nhất).
- Vinh đi đến thư viện theo tuyến đường: 1 → 2 → 3 →5 → 4, chỉ mất chi phí tuyến đường 5→4 là 2.
Giới hạn:
- Có 15% số test ứng với = ;
- Có 15% số test ứng với trường hợp chỉ có đường đi duy nhất từ đến có tổng chi phí nhỏ nhất;
- Có 25% số test ứng với ;
- Có 45% số test còn lại không có ràng buộc gì thêm;
Comments
Updated