기지 간소화

먼 미래, 인류는 수많은 외계 행성에 진출했다. 행성 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 km이다.)
  • 임의의 $u, v$ ($s \le u < v \le e$)에 대해, $u$번 기지와 $v$번 기지는 고른 통로만 이용해서 오갈 수 있다. 비활성화된 기지를 거쳐 가도 된다.
• 고른 통로 길이의 합이 $C$ km일 때, 유지 비용은 $C$이다.

• $2 \le N \le 250\,000$
• 모든 $i$에 대해 $0 \le U[i], V[i] \le N-1$이고 $U[i] \neq V[i]$이다 ($0 \le i \le N-2$)
• 모든 $i$에 대해 $1 \le W[i] \le 10^9$이다 ($0 \le i \le N-2$)