작은 마을의 이장이 된 현서는 이 마을의 모든 도로가 비포장임을 깨달았다.

이에 현서는 주민들의 편의를 위해, 마을에 있는 도로를 포장하려고 한다.

이 마을에는 N개의 농가가 있고, (N-1)개의 도로가 있으며, 어떤 두 농가를 골라도, 한 곳에서 다른 곳으로 가는 경로는 유일하다.

현서의 마을은 예산이 한정적이기 때문에, 최대한 적은 예산으로 모든 도로를 포장하려고 한다.

도로를 포장하기로 한 날, 마을 주민들은 각자의 거주지에서 다른 농가로 농사를 지으러 갈 것이다.

구체적으로, i번 주민은 이 날 농가 x_i에서 농가 y_i로 트랙터를 타고 농사를 지으러 간다.

트랙터는 각각 고유의 값 c_i를 가지고 있는데, c_i가 낮을수록 좋은 트랙터이다.

현서는 어떤 주민의 이동 경로가 비포장이면, 해당 주민의 도움을 받아 도로 하나당 c_i의 비용을 들여 그 경로상에 있는 어떤 도로든지 포장할 수 있다.

두 명 이상의 주민이 같은 도로를 지나간다면, 그 중 어느 주민의 도움을 받든 상관이 없다.

어떤 도로는, 외부 업체의 도움을 받는 것이 나을 수도 있다.

(혹은 외부 업체를 부르는 선택지밖에 없을 수도 있다.)

외부 업체의 경우, 어느 도로든 상관없이 도로 하나당 K의 비용을 들여 포장할 수 있다.

예를 들면, 아래의 그림 1과 같은 마을이 있고 이 마을에 주민이 2명 살고 있다고 하자.

(그 마을은 정말 고요할 것이다.)

외부 업체에서 도로 하나를 포장하는 비용 K=5라고 하자.

그림 1

한 주민은 4번 농가에서 3번 농가로 c1=1의 트랙터를 타고 이동할 계획이며.

다른 주민은 5번 농가에서 6번 농가로 c2=3의 트랙터를 타고 이동할 계획이라고 하자.

그러한 경우는 그림 2와 같이 14의 비용을 들여 모든 도로를 포장할 수 있다.

그림 2

현서가 모든 도로를 포장하는 최소비용을 계산하는 프로그램을 작성하라.

도로포장 timer 2s memory 128MB

도로포장 2s 128MB