Cây con lớn nhất

Cho một cây (đơn đồ thị vô hướng liên thông, không có chu trình) gồm $N$ đỉnh, đánh số từ $1$ đến $N$, với các cạnh có trọng số. Trọng số của một cây được định nghĩa bằng tổng trọng số các cạnh của nó.

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 đầu mút bị xóa). Cây con phải liên thông và còn lại ít nhất một đỉnh; được phép không xóa đỉnh nào (giữ nguyên cả cây). Cây con chỉ gồm một đỉnh có trọng số $0$.

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 số $N$ là số đỉnh của cây $(1\le N\le 50000)$.
• $N-1$ dòng sau, mỗi dòng ghi ba số nguyên $u,v,c$ thể hiện một cạnh của cây nối hai đỉnh $u,v$, có trọng số là $c$ $(1\le u,v\le N,u\ne v,-10000\le c\le 10000)$. Các cạnh đảm bảo tạo thành một cây.

Dữ liệu ra

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

Ràng buộc

• $1\le N\le 50000$.
• $1\le u,v\le N$, $u\ne v$, $-10000\le c\le 10000$.

Ví dụ