15940번 - 네트워크 해킹

1번부터 N번까지 번호가 붙어있는 N개의 컴퓨터로 구성된 컴퓨터 네트워크가 있다. 그 사이에는 두 컴퓨터를 직접 연결하는 회선이 N-1개 설치되어있다. 이 네트워크는 모든 컴퓨터 사이에 통신이 가능하다. 즉, 임의의 컴퓨터에서 시작하여 직접 연결된 회선들을 계속 따라가면 다른 모든 컴퓨터와 연결되어 통신할 수 있다.

각 회선마다 그 회선에 직접 연결되어있는 한쪽 컴퓨터에서 다른쪽 컴퓨터로 데이터를 보내는데 걸리는 시간이 고유하게 존재한다. 따라서 데이터가 여러 회선을 통해 전송되는데 걸리는 총 전송시간은 그 데이터가 지나간 회선들의 전송시간 각각을 더한 값이 된다.

임의의 u번 컴퓨터에서 다른 v번 컴퓨터로 데이터를 전송할 때는, u번 컴퓨터에서 출발해 v번 컴퓨터로 도착하는 경로 중 총 전송시간이 가장 작은 경로로 데이터가 움직인다. 이 때의 총 전송시간이 u, v 사이의 데이터 전송시간이 된다.

‘최대 전송시간’은 네트워크 안의 임의의 두 컴퓨터 사이의 데이터 전송시간 중 가장 큰 값으로 정의된다. 이 ‘최대 전송시간’의 값으로 컴퓨터 네트워크의 가치가 결정된다. 즉, ‘최대 전송시간’ 이 작을 수록 가치가 높은 네트워크인 것이다.

세계 최고의 해커를 꿈꾸는 성원이는 해킹 실력을 기르려면 우선 물리적 해킹부터 연습해봐야겠다고 생각했다. 마침 평소에 이 네트워크에 대해 불만이 많았으므로, 이 네트워크를 타겟으로 삼아 물리적 해킹을 해보기로 했다. 구체적으로 다음과 같은 과정을 통해 이 네트워크를 공격하려고 한다.

1. 네트워크에 존재하는 회선 중 하나를 골라 그 회선을 끊는다.
2. 서로 다른 두 컴퓨터를 고른 후, 아까 끊은 그 회선과 동일한 전송시간을 갖는 회선을 그 사이에 설치한다.
3. 사람들이 네트워크가 공격당했다는 것을 눈치채면 안되기 때문에, 회선을 끊고 다시 설치한 후에도 모든 컴퓨터 사이에 통신이 가능해야 한다.

성원이는 위 과정을 딱 한 번만 수행해 이 네트워크의 가치를 최대한 떨어뜨리려고 한다. 즉, 해킹을 마친 상태에서 계산한 ‘최대 전송시간’ 이 가장 커지는 선택을 단 한 번만 할 것이다.

네트워크 안의 컴퓨터 수가 매우 많으므로 프로그램을 만들어 계산해야 하는데 성원이는 프로그래밍을 할 줄 모른다. 4차산업혁명 시대에 프로그래밍도 모르는 불쌍한 성원이를 도와주자.

첫 번째 줄에 네트워크 상의 컴퓨터 수 N(2 ≤ N ≤ 200,000)이 주어진다.

두 번째 줄부터 N-1줄에 걸쳐 네트워크의 회선 정보가 주어진다. 각 줄마다 세개의 자연수 a, b, t (1 ≤ a, b ≤ N, a ≠ b, 1 ≤ t ≤ 10⁷) 가 주어지는데, 이는 a번 컴퓨터와 b번 컴퓨터 사이를 직접 연결하는 회선이 존재하며, 그 회선의 전송시간이 t초 라는 뜻이다.

첫 번째 줄에 최선의 해킹을 했을 때 가능한 ‘최대 전송시간’의 최댓값을 출력한다.