드워프들은 방금 새로운 지하 마을을 건설했습니다. 이제 마을 안에서 운행할 철도망을 계획할 때입니다.
마을은 $N$개의 교차로와 이를 연결하는 $N - 1$개의 터널로 이루어져 있습니다. 터널들은 어떤 교차로에서든 다른 모든 교차로로 이동할 수 있도록 건설되었습니다. 막다른 길(즉, 오직 하나의 터널로만 연결된 교차로)인 각 교차로에는 기차역이 있습니다.
당신의 과제는 마을의 기차 노선을 결정하는 것입니다. 드워프들의 요구사항을 충족하기 위해 모든 기차역은 둘씩 짝지어져야 하며(다행히 기차역의 수는 짝수입니다), 각 쌍의 역 사이에는 가능한 최단 경로를 이용하는 기차가 한 대씩 운행됩니다. 하지만 터널에는 한계가 있습니다. 모든 터널의 길이는($1$로) 같지만, 터널의 폭 때문에 통과할 수 있는 노선의 수에는 제한이 있습니다.
드워프들은 기차 노선들의 총길이를 가능한 한 길게 만들고 싶어 합니다. 가능한 최대 총길이가 얼마인지 계산할 수 있습니까?
입력
입력의 첫 번째 줄에는 마을의 교차로 수를 나타내는 하나의 정수 $N$이 주어집니다.
다음 $N - 1$개의 각 줄에는 세 정수 $a_i$, $b_i$, $c_i$가 주어지며, 이는 교차로 $a_i$와 $b_i$ 사이에 터널이 있음을 나타냅니다. 값 $c_i$는 이 터널을 통과할 수 있는 노선 수의 상한입니다.
출력
첫 번째이자 유일한 줄에 선택된 역 쌍들 사이의 경로들의 최대 총길이를 나타내는 정수 하나를 출력합니다.
제약 조건을 만족하면서 역들을 짝짓는 방법이 없다면 $-1$을 출력합니다.
제한
$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, 모든 교차로는 연결되어 있으며, 역(즉, 막다른 길)의 수는 짝수입니다.
예제
예제 입력 1
10 1 2 2 2 3 1 3 4 3 5 1 1 6 1 2 7 2 3 8 3 2 9 3 1 10 4 7
예제 출력 1
10
노트
첫 번째 예제에서 교차로 $5\text{--}9$, $6\text{--}7$, $8\text{--}10$에 있는 역들을 연결하면 기차 노선의 총길이가 $4 + 3 + 3 = 10$이 됩니다.
예제 입력 2
5 1 2 3 1 3 1 1 4 0 1 5 2
예제 출력 2
-1