Cho một cây với các cạnh có trọng số. Trọng số của cây được định nghĩa bằng tổng trọng số các cạnh. Một cây con là cây thu được bằng cách xóa đi một số đỉnh và các cạnh có ít nhất một đỉnh bị xóa. Yêu cầu: Cho một cây, hãy tìm cây con có trọng số lớn nhất.

Dữ liệu vào

• Dòng đầu ghi ~ n ~ là số đỉnh của cây;
• ~ n-1 ~ dòng sau, mỗi dòng ghi 2 số ~ u,v,c ~ ~ (1 ≤ u, v ≤ n ) ~ thể hiện một cạnh của cây nối hai đỉnh ~ u,v ~ có trọng số là ~ c ~.

Kết quả

Ghi ra một số nguyên duy nhất là trọng số lớn nhất có thể có của một cây con.

Ràng buộc

• ~ 1 <= n <= 5.10^4 ~
• ~ -10^4 <= c <=10^4 ~

Ví dụ:

Input 1

5
5 1 2
1 2 -5
2 3 1
2 4 2 

Output 1

3