Công ty Viễn thông muốn thu gọn hệ thống mạng cáp quang của mình. Biết rằng hệ thống mạng hiện tại của công ty gồm \(n\) nút mạng, giữa hai nút mạng bất kỳ đều có đường kết nối trực tiếp hoặc gián tiếp với nhau. Bạn hãy giúp công ty chọn phương án thu gọn sao cho giữa hai nút mạng bất kỳ vẫn có đường kết nối trực tiếp hoặc gián tiếp với nhau mà tổng chiều dài cáp quang toàn mạng còn lại là ít nhất.

Dữ liệu vào

• Dòng đầu ghi số nguyên dương \(N\) (\(N \le 1000\) là số nút mạng );
• Những dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên \(u, v\) và \(d\), cho biết hai nút \(u\) và \(v\) có kết nối trực tiếp bằng cáp quang chiều dài \(d\).

Dữ liệu ra

• Số nguyên \(S\) là tổng chiều dài cáp quang ít nhất được giữ lại cho cả hệ thống.

Input 1

5 
1 2 1
1 3 4
1 4 20
2 3 15
2 4 3
3 5 3
3 4 1
3 5 3
4 5 2

Output 1

7