Công ty viễn thông VietTel đang vận hành một mạng gồm \(N\) trạm phát sóng được kết nối với nhau bởi \(N - 1\) tuyến cáp quang hai chiều. Mỗi tuyến cáp có một độ trễ truyền tín hiệu \(w\) mili-giây; độ trễ có thể âm nếu tín hiệu được khuếch đại tại trạm tiếp theo. Kỹ sư Lan muốn tìm một đường truyền đơn (không qua trạm nào quá một lần) giữa hai trạm bất kỳ sao cho tổng độ trễ là lớn nhất; đường truyền có thể chỉ gồm một trạm duy nhất, lúc đó tổng độ trễ coi như \(0\).

Hãy giúp kỹ sư Lan tìm tổng độ trễ lớn nhất.

Định dạng đầu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 2 \times 10^5\)).
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\) và \(w\) (\(1 \le u, v \le N\), \(-10^5 \le w \le 10^5\)).

Định dạng đầu ra

• In ra tổng độ trễ lớn nhất trên một đường truyền đơn bất kỳ.

Ví dụ

Input:

4
1 2 5
2 3 -2
2 4 3

Output:

8

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 100\).
• \(30\%\) số điểm ứng với \(N \le 5000\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.