Farmer John cần vận chuyển sữa của mình đến các điểm bán hàng. Trong quá trình vận chuyển, sữa có thể được chuyển đến một số điểm bán hàng trước, sau đó từ các điểm này chuyển tiếp đến các điểm khác. Tổng khoảng cách vận chuyển càng nhỏ thì chi phí vận chuyển càng thấp.
Farmer John mong muốn vận chuyển với chi phí thấp, nhưng ông không muốn đối thủ cạnh tranh biết được phương án vận chuyển cụ thể của mình, vì vậy ông hy vọng sử dụng phương án vận chuyển có chi phí nhỏ thứ hai thay vì nhỏ nhất. Hãy giúp ông tìm ra phương án vận chuyển đó.
Dữ liệu:
Dòng đầu tiên là hai số nguyên , biểu thị số đỉnh và số cạnh.
dòng tiếp theo, mỗi dòng gồm 3 số nguyên , biểu thị một con đường nối hai đầu với khoảng cách .
Kết quả:
Duy nhất một dòng, xuất ra chi phí của phương án nhỏ thứ hai.
Ví dụ:
Dữ liệu:
4 4
1 2 100
2 4 200
2 3 250
3 4 100
Kết quả:
450
Giới hạn: , dữ liệu có thể có cạnh lặp (multigraph).
