집게

그림 1처럼 이진 트리 모양으로 생긴 중장비가 있다. 여기서 이진 트리란 잎이 아닌 노드가 자식을 최대 두 개까지 갖는 트리다. 트리의 간선은 금속 막대이고, 막대끼리는 트리의 노드에 놓인 경첩으로 이어진다. 그림에서 노드에는 1부터 5까지 번호가 붙어 있다. 그림 1(a)에서 트리의 잎 노드는 중장비가 힘든 작업을 할 때 쓰는 집게다. 집게도 경첩으로 금속 막대에 연결된다.

그림 1: (a) 트리와 (b) 그에 대응하는 집게 트리.

중장비는 하중을 견뎌야 하므로 금속 막대를 잇는 경첩은 등급이 맞아야 한다. 트리의 노드 $v$에서 쓰는 경첩의 등급은 (i) $v$를 뿌리로 하는 서브트리에 속한 금속 막대의 무게 합과 (ii) $v$에서 트리의 루트까지 가는 길에 놓인 금속 막대의 무게 합을 더한 값이다.

그림 1에는 각 간선 옆에 그 금속 막대의 무게를 적어 두었다. 집게와 경첩은 초경량 소재라서 무게가 없다고 본다. 그래서 집게를 금속 막대에 잇는 잎 노드 1, 2, 3의 경첩 등급은 각각 50, 30, 50이다. 노드 4의 경첩 등급은 60이고, 루트 노드 5의 경첩 등급은 110이다.

집게의 무부하 하중은 그 집게에서 루트 노드까지 가는 경로에 놓인 경첩 등급을 모두 더한 값이다. 이 예에서 무부하 하중은 노드 1의 집게가 220, 노드 2의 집게가 200, 노드 3의 집게가 160이다. 주어진 중장비의 집게 중에서 무부하 하중의 최댓값을 출력하라.

입력은 $n$개의 줄로 이루어진다. 첫째 줄에 이진 트리의 노드 개수 $n$ ($1 \le n \le 12000$)이 주어진다. 이어지는 $n - 1$개의 줄에는 공백으로 구분된 정수 세 개가 주어진다.

• thisnode: 현재 노드의 번호
• parnode: 현재 노드의 부모 노드 번호
• weight: 현재 노드와 부모 노드를 잇는 금속 막대의 무게. 100 이하의 양의 정수다.

노드에는 1부터 $n$까지 번호가 붙어 있다. 부모가 없는 노드가 루트다.

주어진 중장비의 집게 중에서 무부하 하중의 최댓값을 정수 하나로 출력한다.