Bò ghét thể dục (bài tập), nhưng hơi thích chạy bộ. Chúng khảo sát đồng cỏ và liệt kê mọi đường có thể. Đường “có hướng”, chỉ đi một chiều. Đôi khi hai đường khác nhau nối hai điểm theo hai hướng ngược nhau.

Hãy tìm “lộ trình vòng” ngắn nhất để chạy. Nó bắt đầu và kết thúc cùng nơi. Độ dài là tổng độ dài các đường phải đi khi chạy quanh vòng.

Đường nối hai điểm. Điểm có tên là số nguyên dương liên tiếp từ 1. Khoảng cách là số nguyên dương.

Mọi đồng cỏ cho đều có ít nhất một lộ trình vòng.

Dữ liệu vào

• Dòng $1$: $N$ ($1 \le N \le 2000$), số đường có hướng; tối đa 400 điểm khác nhau.
• Dòng $2..N+1$: đầu, cuối và khoảng cách (tối đa 1000) một đường.

Dữ liệu ra

Một dòng chứa khoảng cách nguyên của vòng ngắn nhất có thể.

Ví dụ

Dữ liệu vào 1

4
3 1 5
1 2 4
2 3 3
1 3 44

Dữ liệu ra 1

12

Tác giả: Hal Burch và Russ Cox