Dubu có mở một cửa hàng kinh doanh cho thuê xe ôtô điện cho trẻ em. Dịch vụ thuê của Dubu có địa điểm đánh số từ đến và có con đường hai chiều, con đường thứ nối hai đỉnh và nếu chạy xe qua con đường này khách hàng sẽ phải trả đồng. Cứ mỗi lần cho thuê xe, Dubu sẽ cho phép khách hàng chạy một đường đi bất kì nào xuất phát từ và kết thúc tại mà không được đi lại con đường nào quá lần, sau đó khách hàng phải chi trả tổng số tiền ứng với từng con đường mà khách hàng đã đi. Do dạo gần đây kinh tế khó khăn buôn bán ngày càng ế ẩm nên Dubu quyết định tung ra một đợt khuyến mãi cực shock: Sau khi khách hàng đi xong hết toàn bộ chuyến đi, khách hàng sẽ chỉ phải trả số tiền ứng với con đường đắt nhất trong số các con đường đã đi qua (nếu khách hàng đi ít hơn con đường thì trả tiền như bình thường, không áp dụng khuyến mãi). Dubu tự hỏi nếu đợt khuyến mãi này được tung ra thì chi phí ít nhất để di chuyển từ đến là bao nhiêu. Các bạn hãy giúp Dubu tính toán con số này nhé!
Dữ liệu vào:
Dòng đầu tiên bao gồm 3 số nguyên dương ;
dòng tiếp theo miêu tả các con đường, dòng thứ bao gồm ba số nguyên dương .
Dữ liệu đảm bảo có đường đi từ đến .
Dữ liệu ra:
Gồm một số nguyên duy nhất là số tiền ít nhất phải trả để đi từ đến .
Ví dụ:
Dữ liệu vào:
6 7 2
1 2 6
2 3 1
2 4 3
2 5 5
3 6 10
4 6 9
5 6 8
Dữ liệu ra:
14
Dữ liệu vào:
5 5 3
2 1 1
3 2 1
4 3 1
4 5 1
1 5 2
Dữ liệu ra:
2
Giải thích:
Trong test ví dụ : Chọn đường đi . Khi đó chi phí của các đường đi là và
vì ta chỉ lấy đường đi có chi phí đắt nhất nên đáp số là .
