도로 폐쇄

수라바야 시에는 분기점이 $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$)마다 이 조건을 만족하도록 도로를 폐쇄하는 최소 비용을 구하자.

• $2 \le N \le 100\,000$
• $0 \le U[i], V[i] \le N - 1$ (모든 $0 \le i \le N - 2$)
• 어떤 두 분기점도 하나 이상의 도로를 통해 연결되어 있다.
• $1 \le W[i] \le 10^9$ (모든 $0 \le i \le N - 2$)