대한민국 1등 택배사인 구름 택배는 주변 대리점의 물량을 관리할 통합 물류센터를 새로 건설하려고 한다. 물류센터는 기존의 대리점들 중 한 곳을 재개발하여 건설하려고 한다. 아래 그림과 같이 현재 이 지역에는 총 N개의 대리점이 존재하며 (N-1)개의 유통로가 설정되어 있다.

그림 1. 총 다섯개의 대리점(정점)과 각 대리점 사이의 유통 경로

각 유통로에는 이동시 필요한 통행 비용이 존재한다. 또한 유통로는 변경되지 않으며, 여러개의 유통로를 경유해 서로 다른 두 대리점간에 화물을 유통할 수 있다. 서로 다른 두 대리점 사이에는 오직 하나의 경로만이 존재하며, 경로가 존재하지 않는 경우는 없다.

물류센터는 N개의 대리점들 중 하나를 선택해 건설할 수 있다. 물류센터는 주기적으로 각 대리점에 화물을 전달하거나 대리점으로부터 화물을 수령해와야 하므로 어떤 대리점에 물류센터를 만드냐에 따라 비용적인 차이가 발생하게 된다. 그렇기에 당신은 다음과 같은 조건을 만족하는 대리점을 찾아 물류센터로 확장하려고 한다.

• 다른 모든 대리점으로 향하는 통행 비용들의 총 합이 최소가 되는 대리점을 물류센터로 결정한다.

예를 들어서 0번 대리점을 물류센터로 지정할 경우 다음과 같이 유통 비용이 결정된다.

• 0번 대리점 -> 1번 대리점 : 2
• 0번 대리점 -> 2번 대리점 : 3
• 0번 대리점 -> 3번 대리점 : 9
• 0번 대리점 -> 4번 대리점 : 14
• 총 유통비용 : 2 + 3 + 9 + 14 = 28

그리고 1번 대리점을 물류센터로 지정할 경우에는 다음과 같이 유통 비용이 결정된다.

• 1번 대리점 -> 0번 대리점 : 2
• 1번 대리점 -> 2번 대리점 : 1
• 1번 대리점 -> 3번 대리점 : 7
• 1번 대리점 -> 4번 대리점 : 12
• 총 유통 비용 : 2 + 1 + 7 + 12 = 22

결과적으로 위의 예시에서는 1번 대리점을 물류센터로 확장하는 것이 가장 적은 유통비용이 발생하게 된다. 이 경우 정답은 22가 된다. 이와같이 위의 규칙을 만족하는 물류센터를 건설했을 때 발생하는 최소의 유통 비용을 계산하는 프로그램을 작성하시오.

입력 형식

첫 줄에는 대리점의 수를 나타내는 1이상 10,000이하의 자연수 N이 주어진다. 

이후 총 (N-1)개의 유통로에 대한 정보가 한 줄에 하나씩 주어진다. 유통로의 정보는 세 개의 정수가 u v c와 같은 형식으로 주어진다.

• u와 v는 대리점의 번호를 나타내는 서로다른 두 정수다.
• 대리점의 번호는 0이상 (N-1)이하의 정수다.
• c는 유통로의 비용을 나타내는 1이상 100이하의 자연수다.

출력 형식

유통비용이 최소가 되는 대리점을 물류센터로 결정했을 때, 해당 물류센터의 유통비용을 정수로 출력하시오.