기지 간소화

먼 미래, 인류는 수많은 외계 행성들에 진출하였다. 행성 X도 그 중 하나로, 우주 탐사 기업 MR은 행성 X에 기지들을 지어 탐사 및 자원 채취 활동을 수행하고 있었다.

행성 X에는 $N$ 개의 기지와 기지들을 잇는 $N-1$ 개의 양방향 통로가 있으며, 임의의 서로 다른 두 기지를 통로만을 사용하여 오갈 수 있다. 즉, 행성 X의 기지와 통로는 트리 구조를 이룬다.

기지에는 각각 $0$ 이상 $N - 1$ 이하의 서로 다른 번호가 붙어 있다. 또 모든 $0\le i \le N-2$ 에 대해서 $i$ 번 도로는 $U\[i]$ 번 도시와 $V\[i]$ 번 도시를 연결하며 통로의 길이는 $W\[i]$ km이다.

어느덧 행성 X의 개발도 안정기에 접어들었다. 모든 기지와 통로를 유지하는 것은 비용이 많이 들기 때문에, MR에서는 일부 기지들만 남기고 나머지를 비활성화하기로 하였다.

어떤 $(s, e)$ ( $0 \le s \le e \le N - 1$ ) 에 대해 $s, s+1, \dots, e$ 번 기지만 남기기로 했다고 하자. 이 때 유지 비용은 다음과 같이 정의된다.

0개 이상의 통로를 골라 다음 조건을 만족시키자. 이 때, 고른 통로들의 길이의 합이 최소가 되도록 고른다. (통로를 $0$ $0$ 개 고른 경우, 길이의 합은 $0$ $0$ km 이다.)
- 임의의 $u, v$ ( $s \le u < v \le e$ )에 대해, $u$ 번 기지와 $v$ 번 기지를 고른 통로들만 이용해서 서로 오고갈 수 있다. 중간에 비활성화된 기지를 거치는 것은 상관 없다.
고른 통로들의 길이의 합이 $C$ km일 때, 유지 비용은 $C$ 이다.