세금 징수원

SPLAY-CRT-2 바이러스와 관련된 최근의 의료비 지출 이후, 바이토키아의 수도 바이트그라드의 국고가 비었습니다. 정확히 4일 뒤면 돈이 떨어져 도시의 전기가 끊깁니다. 그 뒤에 어떤 혼란이 벌어질지 상상하기 어렵습니다. 그러니 이런 일은 반드시 막아야 합니다. 예산의 구멍을 메우려면 새로운 세금을 당장 도입해야 합니다.

바이트그라드는 1부터 $n$까지 번호가 붙은 $n$개의 로터리와 이들을 잇는 $n-1$개의 도로로 이루어져 있습니다. 어느 로터리에서든 도로를 따라 다른 모든 로터리에 갈 수 있습니다. 도로가 하나뿐인 로터리도 있는데, 이렇게 허술하게 운영하니 시 국고가 빌 만도 합니다.

각 도로에 사는 주민들은 도시를 살리기 위해 기꺼이 돈을 낼 용의가 있습니다. 도로마다 거기서 세금을 걷었을 때 얻을 수 있는 예상 수익이 추정되어 있습니다. 장비비와 징수원 보수 같은 여러 비용은 이미 차감된 값이므로, 수익이 음수인 도로도 있을 수 있습니다.

고용된 징수원은 각자 한 로터리에서 일을 시작해 이후 4일 동안 세금을 걷습니다. 하루 동안 징수원은 도로 하나를 따라 한쪽 끝에서 다른 끝으로 이동하며 세금을 걷습니다. 다음 날에는 전날 일을 마친 로터리에서 나가는 나머지 도로 중 하나를 택해 세금을 걷습니다. 재정 상황이 절박하므로 징수원들은 4일 동안 쉬지 않고 일해야 합니다. 따라서 각 징수원은 바이트그라드의 두 로터리 사이 경로를 이루는 정확히 4개의 도로에서 세금을 걷습니다. 또한 사회적 소요를 막기 위해 어떤 도로에서도 세금을 두 번 걷어서는 안 됩니다.

첫 줄에는 로터리의 개수를 나타내는 정수 $n$ ($2 \le n \le 2 \cdot 10^5$)이 주어집니다. 이어지는 $n-1$개의 줄에는 각각 세 정수 $u_i$, $v_i$, $z_i$ ($1 \le u_i, v_i \le n$, $-10^9 \le z_i \le 10^9$)가 주어집니다. 이는 로터리 $u_i$와 $v_i$가 도로로 연결되어 있고, 그 도로에서 세금을 걷으면 $z_i$ 바이트랄러의 수익이 생긴다는 뜻입니다.

세금으로 얻을 수 있는 최대 수익을 바이트랄러 단위의 정수 하나로 출력합니다.