마법의 숲

마법사 서연은 마법의 숲을 탐험하고 있다. 숲은 트리 구조로 연결된 N개의 나무로 이루어져 있으며, 루트 노드는 1번이다. 각 간선을 지날 때마다 에너지 포인트를 획득할 수 있다.

루트에서 출발하여 임의의 리프 노드까지 이동할 때, 획득하는 에너지 포인트의 합이 최대가 되는 경로를 찾으시오. 최대 에너지 포인트 합을 출력한다.

마법의 숲 트리47253123456

입력

첫째 줄에 나무의 수 N이 주어진다. 다음 N-1줄에 간선 정보 u, v, w가 주어진다. u와 v를 연결하는 간선의 에너지 포인트는 w이다.

• 1 ≤ N ≤ 100,000
• 1 ≤ w ≤ 10,000

출력

루트에서 리프까지의 최대 에너지 포인트 합을 출력한다.

예제 입력

6
1 2 4
1 3 7
2 4 2
2 5 5
3 6 3

예제 출력

10