시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 137 67 56 51.852%

문제

트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다.

트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리는 두 번째 트리의 지름을 구하려고 한다.

두 번째 트리의 지름은 무엇이냐? 바로 두 번째로 가장 먼 두 정점 간의 거리를 의미한다. (두 번째 트리의 지름은 트리의 지름과 같을 수 있다.)

바로 두 번째 트리의 지름을 구해보자.

입력

첫 번째 줄에는 정점의 개수 N(3 ≤ N ≤ 100,000)이 들어온다.

둘째 줄부터 N번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수와 두 번째 정수는 간선과 연결된 정점 번호를 나타내고, 세 번째 정수는 간선의 가중치를 나타낸다. 간선의 가중치는 20,000 이하의 자연수이다.

출력

첫째 줄에 두 번째 트리의 지름을 출력한다.

예제 입력 1

3
1 2 3
2 3 4

예제 출력 1

4

예제 입력 2

3
1 2 3
1 3 2

예제 출력 2

3

예제 입력 3

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

예제 출력 3

6