양갈래 구하기

평화로운 양갈래의 마을에 위기가 닥쳐왔다! 덩굴에 독이 퍼져 양갈래가 있는 곳으로 옮겨지고 있다!

독은 양갈래의 방을 제외하고, 정확히 한 개의 덩굴로 연결된 방에서부터 옮겨진다.

모든 방의 쌍 사이에는 $1$개 이상의 덩굴을 지나는 유일한 경로가 존재하며, 덩굴은 총 $N-1$개가 존재한다. 각 덩굴의 끝과 끝은 각각의 방에 강하게 연결되어 있어 양갈래의 방까지 독이 스며들지 않도록 덩굴을 잘라야 한다.

또한, 덩굴을 자르기 위해서는 덩굴의 두께 $V$의 힘이 든다. 양갈래의 방까지 독이 가지 않게 덩굴을 잘라야 양갈래를 구할 수 있다. 덩굴을 자르는 데에는 많은 힘이 들기에, 시현이는 가능한 한 적은 힘을 들이며 덩굴을 자르고 싶다.

시현이를 도와 덩굴을 자르기 위해 필요한 힘의 합의 최솟값을 구해주자!

첫 번째 줄에는 방의 수 $N$이 주어진다. $(2 \leq N \leq 100\,000)$

이후 $N-1$개의 줄에 세 정수 $A$, $B$, $V$가 사이에 공백을 두고 주어진다. $(1 \leq A, B \leq N$, $1 \leq V \leq 1\,000)$

이는 $A$번 방과 $B$번 방을 연결하는 덩굴의 두께가 $V$라는 뜻이다.

양갈래가 묶인 방은 $1$로 주어진다.

덩굴을 자르기 위해 필요한 힘의 합의 최솟값을 출력한다.

다음 그림에서 1과 2를 연결하는 덩굴, 3과 6을 연결하는 덩굴, 3과 7을 연결하는 덩굴을 자르면 총 3+1+2로 6의 힘이 최솟값이 된다.