아폴로니안 네트워크

아폴로니안 네트워크는 무방향 그래프이다. 삼각형 하나에서 시작해, 가운데 있는 삼각형을 3개의 작은 삼각형으로 나누는 과정을 재귀적으로 반복해서 만든다.

가중치가 있는 아폴로니안 네트워크에서 가중치 합이 최대인 단순 경로를 찾고, 그 가중치 합을 출력하라.

첫 번째 줄에 정점의 개수 $n$이 주어진다. ($3 \le n \le 250$)

이후 $3(n-2)$개의 줄에 간선의 정보 $a_i$, $b_i$, $c_i$가 주어진다. 이는 정점 $a_i$와 $b_i$를 가중치 $c_i$인 간선으로 잇는다는 뜻이다. ($1 \le a_i, b_i \le n$, $0 \le c_i \le 10^6$)

주어진 그래프는 아폴로니안 네트워크이다.

가중치 합이 최대인 단순 경로의 가중치 합을 출력하라.