철도 노선 덮기

어느 나라의 철도망은 여러 개의 철도 구간으로 이루어져 있습니다. 각 구간은 서로 다른 두 마을을 연결하며, 모든 구간의 길이가 주어집니다. 이 철도망에서는 임의의 두 마을 사이를 잇는 경로가 정확히 하나만 존재합니다.

철도 회사는 새 고속 열차를 운행하기 위해 열차 노선을 다시 정하려고 합니다. 하나의 노선은 두 개 이상의 마을로 이루어진 순서 있는 목록이며, 목록에서 이웃한 두 마을은 반드시 철도 구간으로 직접 연결되어 있어야 합니다. 노선의 길이는 그 노선에 포함된 철도 구간 길이의 합입니다.

열차가 매우 빠르기 때문에 서로 다른 두 노선이 같은 마을을 지나서는 안 됩니다. 모든 마을은 정확히 하나의 노선에 포함되어야 합니다.

위 조건을 만족하도록 노선들을 정할 때, 모든 노선 길이의 합이 최대가 되도록 하세요.

첫째 줄에 마을의 수 N이 주어집니다. 1 <= N <= 2000입니다. 마을은 1번부터 N번까지 번호가 붙어 있습니다.

다음 N-1개 줄에는 철도 구간의 정보가 주어집니다. 각 줄에는 세 정수 A, B, C가 주어지며, 이는 A번 마을과 B번 마을을 잇는 길이 C의 구간을 뜻합니다. 1 <= C <= 1,000,000입니다.

주어지는 입력에는 항상 조건을 만족하는 노선 배치가 존재합니다.

문제의 조건을 만족하는 노선 배치 중, 모든 노선 길이의 합의 최댓값을 첫째 줄에 출력합니다.