구슬이 서말이라도 꿰어야 보배

"구슬 꿰기" 게임에서 실은 빨간색과 파란색 두 가지가 있습니다. 구슬은 1번부터 $n$번까지 번호가 붙어 있습니다. 게임은 구슬 하나로 시작하며, 아래 연산으로 구슬을 추가합니다.

• Append(w, v): 새 구슬 $w$를 기존 구슬 $v$에 빨간 실로 연결합니다.
• Insert(w, u, v): 빨간 실로 연결된 $u$와 $v$ 사이에 새 구슬 $w$를 넣습니다. 기존 빨간 실 $u$-$v$를 제거하고, 파란 실 $u$-$w$, $w$-$v$ 두 개로 바꿉니다.

모든 실은 길이를 가집니다. 게임이 끝났을 때 점수는 파란 실 길이의 합입니다.

최종 연결 상태(구슬 쌍과 실 길이만 주어지고 색은 주어지지 않음)가 주어집니다. 이 상태를 만들 수 있는 모든 방법 중 최종 점수의 최댓값을 구하세요.

첫째 줄에 구슬 수 $n$ ($1 \le n \le 200\,000$).

다음 $n-1$줄에 $a_i$, $b_i$, $c_i$ ($1 \le a_i < b_i \le n$, $1 \le c_i \le 10\,000$). $a_i$와 $b_i$는 연결된 구슬, $c_i$는 실 길이.

가능한 최종 점수 중 최댓값을 출력한다.

예제처럼 3번 구슬에서 시작해 5와 연결한 뒤 1을 3-5 사이에 넣고, 2와 4를 1에 붙이면 60점을 얻을 수 있습니다. 더 큰 점수는 없습니다.