트리 수정

정점이 $N$개인 트리 $T$가 있다. 정점에는 $0$번부터 $N-1$번까지 번호가 붙어 있다.

• 트리에서 두 정점을 잇는 단순 경로는 항상 하나뿐이다.
• 두 정점 사이의 거리는 그 경로에 놓인 간선 가중치의 합이다.
• 트리의 지름은 모든 정점 쌍의 거리 중 최댓값이다.

홍준이는 $T$에서 간선 하나를 지우고 간선 하나를 새로 잇는다. 새로 잇는 간선의 가중치는 지운 간선의 가중치와 같아야 하고, 간선을 이은 뒤에도 그래프는 트리여야 한다. 지운 간선을 그대로 다시 이어도 된다.

이렇게 만들 수 있는 트리 중에서 지름이 가장 큰 값을 구하는 프로그램을 작성하시오.

첫째 줄에 트리 정점의 개수 $N$이 주어진다. ($2 \le N \le 2000$)

둘째 줄부터 $N-1$개의 줄에 간선이 한 줄에 하나씩 주어진다. 각 줄은 세 정수 $from$, $to$, $cost$로 이루어지며, $from$번 정점과 $to$번 정점을 잇는 간선의 가중치가 $cost$라는 뜻이다. ($0 \le from, to \le N-1$, $from \ne to$, $1 \le cost \le 10^9$)

주어지는 그래프는 항상 트리다.

첫째 줄에 홍준이가 만들 수 있는 트리의 지름 중 가장 큰 값을 출력한다.

첫 번째 예제의 트리는 정점이 4개, 간선이 3개다. 처음 지름은 2번과 3번을 잇는 경로이고 길이는 $8 + 4 = 12$다. 1번과 0번을 잇는 간선을 지우고 가중치 2짜리 간선으로 3번과 1번을 이으면, 지름은 2번과 1번을 잇는 경로가 되고 길이는 $8 + 4 + 2 = 14$가 된다.

두 번째 예제에서는 지운 간선을 그대로 다시 잇는 것이 정답이다.