Ở vùng ngoại ô có trạm phát sóng, đường dây cáp đôi, đường dây thứ nối trạm và . Đặc biệt, trạm số là trạm tổng của công ty viễn thông, trạm số nằm trong một trang trại. Hiện tại, chủ trang trại muốn nâng cấp đường truyền, trong đó việc nâng cấp đường dây thứ tốn chi phí .
Công ty điện thoại đang tổ chức chương trình khuyến mãi. Chủ trang trại có thể chỉ định một đường đi từ trạm số đến trạm số , và chỉ định không quá đường dây trên đường đi đó để công ty cung cấp dịch vụ nâng cấp miễn phí. Chủ trang trại chỉ cần thanh toán chi phí cho đường dây có giá nâng cấp đắt nhất trong số các đường dây còn lại trên đường đi (những đường dây không được miễn phí). Hãy tìm chi phí tối thiểu cần thiết để hoàn thành việc nâng cấp.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên .
dòng tiếp theo, mỗi dòng chứa ba số nguyên .
Kết quả:
Nếu không tồn tại đường đi từ đến , xuất ra -1. Ngược lại xuất ra chi phí tối thiểu cần thiết.
