양갈래 구하기

평화로운 양갈래 마을에 위기가 닥쳤다. 덩굴에 독이 퍼져 양갈래가 있는 방 쪽으로 옮겨지고 있다.

독은 양갈래의 방을 제외하고, 덩굴 하나로만 연결된 방에서 퍼져 나온다.

모든 방 사이에는 덩굴을 지나는 유일한 경로가 있고, 덩굴은 모두 $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으로 최솟값이 된다.