Hàng ngày, một khối lượng lớn khí đốt được vận chuyển từ Nga sang các nước Bắc Âu. Người ta mô hình hóa bài toán này như sau: Có điểm trung chuyển để vận chuyển khí đốt. Các điểm trung chuyển được đánh số từ đến . Điểm trung chuyển từ Nga được đánh số là , điểm cần vận tải đến ở Bắc Âu được đánh số . Có con đường nối giữa các điểm trung chuyển này và biết chi phí vận chuyển khi đi qua các con đường này.
Để giảm chi phí vận chuyển, người ta muốn xây dựng không quá đường ống dẫn trên các con đường nối giữa các điểm trung chuyển này. Sau khi xây dựng, chi phí vận chuyển trên các con đường này giảm xuống còn .
Bạn hãy viết chương trình xác định chi phí vận chuyển từ điểm trung chuyển đến là nhỏ nhất mà sau khi đã xây dựng được không quá ống dẫn khí đốt.
Dữ liệu vào:
Dòng đầu ghi ba số ;
dòng tiếp theo, mỗi dòng ghi ba số thể hiện một đường trung chuyển từ đến với chi phí là .
Dữ liệu ra:
Ghi một số duy nhất là chi phí vận chuyển từ điểm trung chuyển đến là nhỏ nhất mà sau khi đã xây dựng được không quá ống dẫn khí đốt.
