Một trò chơi phổ biến thời Leonardo sử dụng các hạt và dây. Dây có màu đỏ hoặc xanh, các hạt được đánh số từ \(1\) đến \(n\). Trò chơi bắt đầu với một hạt duy nhất. Sau đó có thể thêm hạt mới bằng một trong hai thao tác:

• Append(w, v): gắn hạt mới \(w\) vào hạt đã có \(v\) bằng một đoạn dây đỏ.
• Insert(w, u, v): chọn một đoạn dây đỏ đang nối hai hạt \(u,v\), bỏ dây đó và chèn hạt mới \(w\) vào giữa bằng hai đoạn dây xanh \(u-w\) và \(w-v\).

Mỗi đoạn dây có một độ dài. Điểm cuối cùng là tổng độ dài của các dây xanh; dây đỏ không đóng góp điểm.

Bạn được cho cấu hình cuối cùng: các cặp hạt nối nhau và độ dài từng dây, nhưng không biết màu dây. Trong số mọi quá trình chơi hợp lệ có thể tạo ra cấu hình này, hãy tìm điểm cuối cùng lớn nhất.

Dữ liệu vào

• Dòng đầu chứa \(n\).
• \(n-1\) dòng tiếp theo, dòng thứ \(i\) chứa \(a_i,b_i,c_i\), cho biết hạt \(a_i\) và \(b_i\) được nối bởi dây dài \(c_i\).

Cấu hình đã cho là một cây.

Dữ liệu ra

In tổng độ dài dây xanh lớn nhất có thể đạt được.

Ràng buộc

• \(1\le a_i<b_i\le n\).
• \(1\le c_i\le10\,000\).
• \(1\le n\le200\,000\).

Ví dụ

5
1 2 10
1 3 40
1 4 15
1 5 20

60

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

140

Giải thích

Ở ví dụ thứ nhất, bắt đầu với hạt \(3\), nối thêm hạt \(5\) bằng dây đỏ tùy ý, chèn hạt \(1\) vào dây \(3-5\) bằng hai dây xanh dài \(40\) và \(20\), rồi nối thêm hạt \(2\) và \(4\) bằng dây đỏ. Tổng độ dài dây xanh là \(60\) và không thể đạt giá trị lớn hơn.

{{asset:apio14-beads-sample1}}

Cấu hình của ví dụ thứ hai có thể đạt điểm \(140\) như hình sau.

{{asset:apio14-beads-sample2}}

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2014, bài Beads and Wires.