전선 연결하기

$N$개의 마을과 두 마을을 양방향으로 잇는 $N-1$개의 도로가 있다. 이 도로만을 이용해 임의의 두 마을 사이를 이동하는 것이 가능하다. 즉, 도로는 트리 형태를 이루고 있다.

두 마을을 잇는 전선 $N-1$개를 설치해 $N$개의 마을을 모두 이으려고 한다. 어떤 두 마을을 전선으로 이을 때 필요한 전선의 길이는 그 두 마을 사이의 거리와 같다. 이때 두 마을 사이의 거리는 두 마을을 잇는 단순 경로를 이루는 도로들의 길이의 합으로 정의된다. 단, 두 마을 사이를 잇는 도로가 있는 경우에는 그 두 마을 사이를 잇는 전선을 설치할 수 없다.

모든 마을을 전선으로 이어서 임의의 두 마을 사이를 전선만으로 오가는 것이 가능한지 판별하고 가능하다면 필요한 전선 길이의 합의 최솟값을 구해보자.

첫째 줄에 마을의 개수를 나타내는 정수 $N$이 주어진다. $(2 \leq N \leq 200\ 000)$

다음 $N-1$줄에 걸쳐 도로를 나타내는 세 정수 $a_i$, $b_i$, $w_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 도로가 $a_i$ 마을과 $b_i$ 마을을 잇고 있으며 길이가 $w_i$임을 나타낸다. $(1 \leq a_i, b_i \leq N; a_i\neq b_i; 1\leq w_i \leq 10^9)$

만약 마을 모두를 전선으로 잇는 것이 불가능하다면 -1을 출력한다. 그렇지 않다면 마을 모두를 잇기 위해 필요한 전선 길이의 합의 최솟값을 출력한다.