N개의 정점으로 이루어진 트리 T가 있다. 트리의 각 정점은 0번부터 N-1번까지 번호가 매겨져 있다.</p>

• 트리에서 임의의 두 정점을 연결하는 단순 경로의 개수는 1개이다.
• 두 정점사이의 거리는 두 정점을 연결하는 단순 경로상에 있는 간선의 가중치의 합이다.
• 트리의 지름은 트리에 존재하는 모든 경로 중에서 가장 긴 것이다.

홍준이는 T에서 간선을 하나 제거하고, 간선을 하나 추가하려고 한다. 이때, 추가하는 간선의 가중치는 제거한 간선의 가중치와 같아야 하며, 간선을 추가한 이후에도 트리를 유지해야 한다.

이때, 홍준이가 만들 수 있는 트리 중에서 지름이 가장 큰 것을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 트리 정점의 개수 N이 주어진다. (2 ≤ N ≤ 2,000)</p>

둘째 줄부터 N-1개의 줄에는 트리를 이루는 간선이 주어진다. 간선은 from, to, cost와 같이 세 가지 정수로 이루어져 있으며, from과 to를 연결하는 간선의 가중치가 cost라는 뜻이다. (1 ≤ cost ≤ 1,000,000,000)

출력 형식

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

예제 입력 1

4
0 1 2
0 2 4
0 3 8

예제 출력 1

14

예제 입력 2

5
0 1 1
1 2 2
2 3 3
3 4 4

예제 출력 2

10

예제 입력 3

12
0 1 100
1 2 1000
0 3 100
3 4 1000
0 5 1
6 5 10
7 5 10
7 8 10
8 9 10
9 10 100
11 9 100

예제 출력 3

2410

예제 입력 4

9
1 6 1
5 6 1
6 4 1
4 8 1
4 0 1
0 3 1
3 2 1
3 7 1

예제 출력 4

7

힌트

예제 1의 경우에 트리는 정점이 4개이고, 간선이 3개있다. 입력으로 주어진 트리의 지름은 2와 3을 연결하는 경로이고 거리는 8+4=12이다.</p>

1과 0을 연결하는 간선을 지우고 3과 1을 연결하는 간선을 추가하면, 트리의 지름은 2와 1을 연결하는 경로가 되고, 길이는 8+4+2=14가 된다.

예제 2의 경우에는 간선을 지우고 같은 간선을 추가하는 것이 정답이다.