도로 폐쇄

수라바야 시는 N개의 분기점이 있는데, 0부터 $N - 1$ 로 번호가 매겨져 있다. 이 분기점들은 $N - 1$ 개의 양방향 도로로 연결되어 있고, 0부터 $N - 2$ 로 번호가 매겨져 있다. 서로 다른 두 분기점을 어떻게 고르더라도 이 둘을 잇는 유일한 경로가 있다. 도로 $i$ ( $0 \le i \le N - 2$ )는 분기점 $U\[i]$ 와 $V\[i]$ 를 연결한다.

환경 문제에 대한 경각심을 높이기 위해서 수라바야 시의 시장 김 박사는 자동차 없는 날을 지정하려고 한다. 자동차 없는 날 행사로, 김 박사는 도로를 폐쇄하려고 한다. 폐쇄할 도로는 다음과 같이 정해진다. 김 박사는 먼저 음이 아닌 정수 $k$ 를 고르고, 모든 분기점에 $k$ 개 이하의 폐쇄되지 않은 도로가 직접 연결되어 있도록 한다. 도로 $i$ 를 폐쇄하는 비용은 $W\[i]$ 이다.

김 박사를 도와서 가능한 음이 아닌 정수 $k$ ( $0 \le k \le N - 1$ ) 각각에 대해 조건을 만족하게 도로를 폐쇄하는 최소 비용을 구하자.

문제

제한