막다른 길 퍼레이드

Treantis는 N개의 교차점(1번부터 N번까지)이 N − 1개의 도로로 연결된 멋진 마을이며, 어떤 교차점에서든 도로를 따라가면 다른 모든 교차점에 도달할 수 있다. 이런 구조 때문에 Treantis에는 정확히 다른 교차점 하나와만 연결된 교차점이 존재하는데, 이런 교차점을 막다른 길(또는 막다른 교차점)이라고 부른다.

마을에 활기를 불어넣기 위해 Treantis 시장은 화려한 퍼레이드가 있는 축제를 열기로 했다. Treantis의 미신 때문에 퍼레이드 경로를 설계할 때 지켜야 할 두 가지 제약이 있다.

1. 각 퍼레이드는 막다른 길에서 출발하여 다른 막다른 길에서 끝나야 하며, 같은 도로를 두 번 이상 지나서는 안 된다.
2. 어떤 두 퍼레이드도 경로에서 공통된 도로를 공유해서는 안 된다. 반면 같은 교차점을 공유하는 것은 문제가 되지 않는다.

시장은 퍼레이드가 교차점 ui와 교차점 vi를 연결하는 도로를 지나면 시민 행복도가 wi만큼 증가한다고 추정했다.

이 문제에서 여러분의 임무는 위의 두 제약을 만족하도록 퍼레이드를 신중히 설계하여 얻을 수 있는 최대 행복도를 계산하는 것이다.

예를 들어 N = 10이고 마을 구조가 다음 그림과 같다고 하자.

보이는 것처럼 막다른 길은 7개이고 그 번호는 {1, 2, 3, 4, 8, 9, 10}이다. 이 예에서 최대 행복도는 다음 경로의 퍼레이드 3개를 운영하여 얻을 수 있다.

• 1 → 5 → 8, 행복도 10 + 30 = 40.
• 2 → 5 → 6 → 9, 행복도 20 + 50 + 20 = 90.
• 4 → 7 → 10, 행복도 40 + 40 = 80.

이 퍼레이드들은 모두 막다른 길에서 시작하고 끝나며, 어떤 두 퍼레이드도 같은 도로를 공유하지 않는다. 이 퍼레이드들의 총 행복도는 40 + 90 + 80 = 210이다. 이 예에서 행복도가 210보다 큰 퍼레이드는 없다.

입력은 정수 N (2 ≤ N ≤ 100 000)이 있는 한 줄로 시작한다. N은 Treantis의 교차점 수이다. 다음 N − 1개의 줄에는 각각 세 정수 ui vi wi (1 ≤ ui < vi ≤ N; 1 ≤ wi ≤ 106)가 주어지는데, 이는 도로와 이 도로를 퍼레이드가 지날 때 증가하는 행복도를 나타낸다. 어떤 교차점에서든 도로를 따라가면 다른 모든 교차점에 도달할 수 있음이 보장된다.

모든 제약을 만족하도록 퍼레이드를 신중히 설계하여 얻을 수 있는 최대 행복도를 나타내는 정수를 한 줄에 출력한다.