#1307. ODAROAD - Làm đường

Tỉnh miền núi zZz có làng, đánh số . Có cặp làng có thể tiến hành ủi đất làm đường. Tỉnh zZz muốn làm đường sao cho làng và làng trở nên liên thông. Hệ thống đường sẽ được hoàn thành dựa vào viện trợ ODA, vốn nhà nước và đóng góp của người dân như sau: Giả sử có con đường được chọn để xây dựng:

• Viện trợ ODA dùng để thực hiện không quá đoạn đường;
• Người dân đóng góp xây dựng đoạn đường dài nhất trong đoạn đường còn lại;
• Vốn nhà nước dùng để thực hiện các đoạn đường còn lại ( đoạn đường cuối cùng)

Hãy xác định số tiền ít nhất người dân phải đóng góp để hoàn thành hệ thống đường đảm bảo liên thông giữa làng và làng .

Dữ liệu vào:

• Dòng đầu chứa ba số nguyên ;
• dòng tiếp theo, dòng thứ chứa ba số nguyên chỉ hai làng có thể xây dựng đường nối trực tiếp với chi phí .

Dữ liệu ra:

• Một số nguyên kết quả, số này bằng nếu không có cách xây dựng đường.

Ví dụ:

Dữ liệu vào:

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

Dữ liệu ra:

4